SamCoding Round 10 (Div. 4) F - Ant Colony
- サイト
- SamCoding
- コンテスト
- SamCoding Round 10 (Div. 4)
- 問題
- F - Ant Colony(常設版)
頂点の重み付きの木が与えられ、 本目の辺は頂点 と を長さ で結んでいます。 頂点間の距離の最大値、つまり木の直径を求める問題です(、)。
木の直径は、次の手順で求められます。
- 適当な頂点から最も遠い頂点 を求める。
- から最も遠い頂点 を求める。 と の距離が直径。
辺の重みが非負なので、重み付きでもこの方法が使えます。各頂点からの距離は DFS や BFS で求められるので、計算量は です。答えは最大で 程度になるので、64 ビット整数で計算します。
C++
#include "shogo-library/base/all"#include "shogo-library/graph/tree.hpp"#include "shogo-library/graph/tree_util.hpp"
void solve() { LL(N); Tree<ll> tree(N); tree.read(-1, true); print(tree_diameter(tree));}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}tree.read(-1, true) で、頂点番号を 0 始まりにずらし、重み付きの辺として読み込んでいます。tree_diameter は上の方法で直径の長さを求める関数です。
使用ライブラリ:cpp_include@cb82602