No.019 D

まずは頂点 $1$ と頂点 $k$ ($k \geq 2$) の距離を問い合わせる. これを $D_k$ とする. なお $D_1 = 0$ とおける.

ここで, $D_k$ が最も大きい頂点を $s$ とする. 任意の2頂点間の距離を $D_{i,j}$ とすると, $D_{i,j}$ が最大となるとき, $i = s$ または $j = s$ が成り立つ. すなわち, 最長距離となる2頂点の片方は $s$ である. (証明は省くが, $s$ でない2頂点 $i, j$ を仮定して $s, i, j$ の位置関係ごとに $i$ または $j$ を $s$ と入れ替えた方が長い距離になることが示せる)

よって, 次に頂点 $s$ と頂点 $k$ ($k \geq 2$ かつ $k \neq s$) の距離を問い合わせ, $D_s$ とこの問い合わせの結果の中の最大値が木の直径である.