コンテンツにスキップ

SamCoding Round 10 (Div. 4) F - Ant Colony

サイト
SamCoding
コンテスト
SamCoding Round 10 (Div. 4)
問題
F - Ant Colony(常設版)

nn 頂点の重み付きの木が与えられ、ii 本目の辺は頂点 uiu_i と viv_i を長さ wiw_i で結んでいます。22 頂点間の距離の最大値、つまり木の直径を求める問題です(n≤2×105n \le 2 \times 10^5、1≤wi≤1091 \le w_i \le 10^9)。

木の直径は、次の手順で求められます。

  1. 適当な頂点から最も遠い頂点 uu を求める。
  2. uu から最も遠い頂点 vv を求める。uu と vv の距離が直径。

辺の重みが非負なので、重み付きでもこの方法が使えます。各頂点からの距離は DFS や BFS で求められるので、計算量は O(n)O(n) です。答えは最大で 2×105×1092 \times 10^5 \times 10^9 程度になるので、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