# パ研合宿2023　第2日「パ研杯」<br/>H - Two PCities

$X, Y$ の近い方までの距離を最大化する頂点 $a$ について考える


$X - Y$ パスの中点で二分すると，左は $X$ の方が近く，右は $Y$ の方が近い


$a$ が左側にあると仮定すると，$a$ は左側に属する頂点の中で最も $X$ から遠い
→ 左側の木の直径の端点である


対称性から右側も同様

$X - Y$ パスの中点が頂点の場合 :


この $2$ つの部分木の直径の端点が分かれば良い

$X - Y$ パスの中点が辺の場合 :


この $2$ つの部分木の直径の端点が分かれば良い

すべての部分木の直径は全方位木 DP で $O(N)$ 時間でわかる

その他の処理は木の LCA, LA, 木上の距離を求めるもので，$\langle O(N), O(1)\rangle$ 時間でできることが知られている