競プロ典型90問 003

Longest Circular Road（★4）

この問題のポイントは

ある頂点から最大距離にある頂点は、全体の最大距離を作る頂点のうちのひとつ

です。

以下、証明（？）をします。

葉を削っていくと最後に残るもの

木に対して以下の操作をします

1. すべての葉に印を付ける
2. 印を付けた葉をすべて消す
3. 残っているものがあれば1に戻る

このとき、最後に残るもの（全部消える直前の状態）は

• 頂点1つ
• 2頂点と辺1つ

の2つがあります。

この最後に残る頂点は「（削除作業前の状態の）最も近い葉までの距離」が全頂点の中で最大です。

中心部分

ここで「中心部分」という言葉を定義します。この記事限定の定義です。

• 最後に残ったものが頂点1つの場合は、その頂点
• 最後に残ったものが頂点2つと辺1つの場合は、その辺

です。

最大距離のパスは中心部分を通る

最大距離のパスが中心部分を通ることは明らかです。

よって、最大距離のパスが複数あったときも、この中心部分を共有します。

ある頂点から一番遠い頂点

ある頂点から一番遠い頂点へのパスは自分のグループ（中心部分を通らないでアクセスできる範囲）内に収まりません。中心部分を通って別グループの一番遠い頂点に行きます。この一番遠い頂点は木全体で最大距離を作る頂点のうちのひとつです。

（「ある頂点」として中心部分の頂点を選んだ場合の記述は省きます。）

以上より

ある頂点から最大距離にある頂点は、全体の最大距離を作る頂点のうちのひとつ

と言えます。