This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 木に対するDFS (対象となる頂点から最も遠い頂点の情報を返す)
// n := (頂点番号, その頂点までのコスト)
// Verified: AtCoder Regular Contest 022 C (ロミオとジュリエット)
// 木の中心を求めるアルゴリズム O(|V|)
// ・まずは、木の最遠点対と、この 2 点から任意の点との距離をそれぞれ求める
// ・木の中心とは、頂点 u から任意の頂点 x までの最短距離の最大値を最小化する頂点 u である
// -> これは、木の直径の真ん中の点に当たるので、該当する点を vector に追加する
// ・木の中心は高々 2 個である
template <typename T>
void dfs(int p, vector< vector< Edge<T> > > &G, vector<T> &dist) {
if(dist[p] == -1) dist[p] = 0;
int cur = dist[p];
for(size_t i=0; i<G[p].size(); i++) {
int to = G[p][i].to; T cost = G[p][i].cost;
if(dist[to] != -1) continue;
dist[to] = cur + cost;
dfs(to, G, dist);
}
}
template <typename T>
vector<int> getCenters(vector< vector< Edge<T> > > &G) {
int n = (int)G.size();
vector<T> d0(n, -1), d1(n, -1), d2(n, -1);
dfs(0, G, d0);
int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
dfs(p1, G, d1);
int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
dfs(p2, G, d2);
vector<int> ret;
T diameter = d2[p1];
for(int i=0; i<n; i++) {
bool b1 = (d1[i] + d2[i] == diameter);
bool b2 = (d1[i] == diameter / 2 || d2[i] == diameter / 2);
if(b1 && b2) ret.push_back(i);
}
return ret;
}
// 木の直径の端点を求める
template <typename T>
tuple<int, int, T> diameter(vector< vector< Edge<T> > > &G) {
int n = (int)G.size();
vector<T> d0(n, -1), d1(n, -1);
dfs(0, G, d0);
int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
dfs(p1, G, d1);
int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
T d = *max_element(d1.begin(), d1.end());
return make_tuple(p1, p2, d);
}
#line 1 "graph/graph_007_tree_dfs.cpp"
// 木に対するDFS (対象となる頂点から最も遠い頂点の情報を返す)
// n := (頂点番号, その頂点までのコスト)
// Verified: AtCoder Regular Contest 022 C (ロミオとジュリエット)
// 木の中心を求めるアルゴリズム O(|V|)
// ・まずは、木の最遠点対と、この 2 点から任意の点との距離をそれぞれ求める
// ・木の中心とは、頂点 u から任意の頂点 x までの最短距離の最大値を最小化する頂点 u である
// -> これは、木の直径の真ん中の点に当たるので、該当する点を vector に追加する
// ・木の中心は高々 2 個である
template <typename T>
void dfs(int p, vector< vector< Edge<T> > > &G, vector<T> &dist) {
if(dist[p] == -1) dist[p] = 0;
int cur = dist[p];
for(size_t i=0; i<G[p].size(); i++) {
int to = G[p][i].to; T cost = G[p][i].cost;
if(dist[to] != -1) continue;
dist[to] = cur + cost;
dfs(to, G, dist);
}
}
template <typename T>
vector<int> getCenters(vector< vector< Edge<T> > > &G) {
int n = (int)G.size();
vector<T> d0(n, -1), d1(n, -1), d2(n, -1);
dfs(0, G, d0);
int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
dfs(p1, G, d1);
int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
dfs(p2, G, d2);
vector<int> ret;
T diameter = d2[p1];
for(int i=0; i<n; i++) {
bool b1 = (d1[i] + d2[i] == diameter);
bool b2 = (d1[i] == diameter / 2 || d2[i] == diameter / 2);
if(b1 && b2) ret.push_back(i);
}
return ret;
}
// 木の直径の端点を求める
template <typename T>
tuple<int, int, T> diameter(vector< vector< Edge<T> > > &G) {
int n = (int)G.size();
vector<T> d0(n, -1), d1(n, -1);
dfs(0, G, d0);
int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
dfs(p1, G, d1);
int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
T d = *max_element(d1.begin(), d1.end());
return make_tuple(p1, p2, d);
}