ABC 401-500/ABC428E - Farthest Vertex - 競技プログラミング用 知識集積所

---

問題

ABC428E

必要知識

B以下レベルの内容は省略

• 木の直径※
• 幅優先探索※（木なので深さ優先探索※でもいい）

考え方

最も遠い点は、木の直径※である。
よって、直径の両端からそれぞれで幅優先探索※をして、各頂点から遠い方の端を答えればよい。

問題は、等距離である場合は頂点番号が最大であるものを答えるという点。
しかし、実はこれは木の直径※を探すアルゴリズムの都合上

• 直径を探すときに、等距離なら頂点番号が大きい方を採用する
• 最後の比較で、等距離なら頂点番号が大きい方を採用する

の2つだけで自然と解決される。

解答例

解答例

注意点

別解