# GRL_5_a 木の直径

GRL_5_a 木の直径
Feb. 2, 2020, 1:52 p.m.

## 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A

## 解説

そこをさらに出発点としたときの最も遠い頂点との距離が直径に等しい.

## 計算量

$O(V)$

## 解答

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #define N_MAX 100001 typedef struct Edge { Int v, w; }Edge; Int N; Int d[N_MAX]; vector edges[N_MAX]; Int bfs(Int u) { loop(i,0,N) { d[i] = -1; } queue Q; Q.push(u); d[u] = 0; while (!Q.empty()) { Int parent = Q.front(); Q.pop(); for (auto child: edges[parent]) { if (d[child.v] != -1) continue; Q.push(child.v); d[child.v] = d[parent] + child.w; } } Int maxIndex = 0; loop(i,1,N) { if (d[maxIndex] < d[i]) maxIndex = i; } return maxIndex; } Int diametar() { Int u = bfs(0); Int v = bfs(u); return d[v]; } int main(void) { Int u, v, w; cin >> N; while (cin >> u >> v >> w) { edges[u].push_back({v, w}); edges[v].push_back({u, w}); } cout << diametar() << endl; }