実装例
問題例
| # | ソース | 難易度 |
|---|---|---|
| AOJ GPL_5 - 木の直径 | - | |
| ABC019 D - 高橋くんと木の直径 | ABC019 D | ★★ |
| ARC022 C - ロミオとジュリエット | ARC022 C | ★★★ |
木の直径
説明
非負の重み付き無向木の直径を求める。適当な頂点 s から最も遠い頂点 u を求める。次に u から最も遠い頂点 v を求める。このとき、(u, v) が最遠頂点対であり、すなわち木の直径である。
情報
| 項目 | データ |
|---|---|
| 計算量 | $O(E)$ |
関数
| Diameter(tree) | |
|---|---|
| 機能 | $tree$ の直径を求める。 |