This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/tree_diameter" #include <bits/stdc++.h> using namespace std; using ll = long long; #include "../tree_diameter.hpp" void solve(int ith) { int n; cin >> n; vector<vector<pair<int, int>>> tree(n); for(int i = 0; i < n - 1; ++i){ int u, v, w; cin >> u >> v >> w; tree[u].emplace_back(v, w); tree[v].emplace_back(u, w); } auto [diameter, path] = get_diameter(tree); cout << diameter << ' ' << path.size() << '\n'; for(auto v: path) cout << v << ' '; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc = 1; // cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); }
#line 1 "tree/test/Tree_Diameter.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/tree_diameter" #include <bits/stdc++.h> using namespace std; using ll = long long; #line 1 "tree/tree_diameter.hpp" pair<ll, vector<int>> get_diameter(const vector<vector<pair<int, int>>>& g) { int n = g.size(); vector<ll> dist(n); vector<int> parent(n); auto dfs = [&](auto self, int u, int fu, ll cur_dist) -> void { dist[u] = cur_dist; parent[u] = fu; for (auto [v, cost] : g[u]) if (v != fu) { self(self, v, u, cur_dist + cost); } }; dfs(dfs, 0, -1, 0); // r = furthest node from root int r = max_element(dist.begin(), dist.end()) - dist.begin(); dfs(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 10 "tree/test/Tree_Diameter.test.cpp" void solve(int ith) { int n; cin >> n; vector<vector<pair<int, int>>> tree(n); for(int i = 0; i < n - 1; ++i){ int u, v, w; cin >> u >> v >> w; tree[u].emplace_back(v, w); tree[v].emplace_back(u, w); } auto [diameter, path] = get_diameter(tree); cout << diameter << ' ' << path.size() << '\n'; for(auto v: path) cout << v << ' '; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc = 1; // cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); }