This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
// Index from 0 // g should contains both (u, v) and (v, u) // Return {length, path} // // Tested: // - https://judge.yosupo.jp/problem/tree_diameter // // Tree diameter (weighted) {{{ using ll = long long; pair<ll, vector<int>> tree_diameter(const vector<vector<pair<int,int>>>& g) { int n = g.size(); vector<ll> dist(n); vector<int> parent(n); function<void(int, int, ll)> dfs = [&] (int u, int fu, ll cur_dist) { dist[u] = cur_dist; parent[u] = fu; for (auto [v, cost] : g[u]) if (v != fu) { dfs(v, u, cur_dist + cost); } }; dfs(0, -1, 0); // r = furthest node from root int r = max_element(dist.begin(), dist.end()) - dist.begin(); dfs(r, -1, 0); // r->s = longest path int s = max_element(dist.begin(), dist.end()) - dist.begin(); vector<int> path; for (int x = s; x >= 0; x = parent[x]) path.push_back(x); return {dist[s], path}; } // }}}
#line 1 "Graph/tree_diameter.h" // Index from 0 // g should contains both (u, v) and (v, u) // Return {length, path} // // Tested: // - https://judge.yosupo.jp/problem/tree_diameter // // Tree diameter (weighted) {{{ using ll = long long; pair<ll, vector<int>> tree_diameter(const vector<vector<pair<int,int>>>& g) { int n = g.size(); vector<ll> dist(n); vector<int> parent(n); function<void(int, int, ll)> dfs = [&] (int u, int fu, ll cur_dist) { dist[u] = cur_dist; parent[u] = fu; for (auto [v, cost] : g[u]) if (v != fu) { dfs(v, u, cur_dist + cost); } }; dfs(0, -1, 0); // r = furthest node from root int r = max_element(dist.begin(), dist.end()) - dist.begin(); dfs(r, -1, 0); // r->s = longest path int s = max_element(dist.begin(), dist.end()) - dist.begin(); vector<int> path; for (int x = s; x >= 0; x = parent[x]) path.push_back(x); return {dist[s], path}; } // }}}