考察
木で任意頂点 u からの最大距離は、直径の両端 s,t のどちらかへの距離に等しい。ただし同距離なら頂点番号が大きい方を選ぶという辞書的な tie-break も距離計算へ組み込みたい。距離を組 (元の辺数, 終点番号) の辞書順として扱えば、実際に 10^-100 の浮動小数辺を作らず微小摂動を正確に模倣できる。拡張木でも任意点の最遠点は一つの直径の端点のいずれかなので、二端点への組付き距離の大きい方が答えになる。
採用する候補: 各元頂点 i に微小な長さ i·ε の葉 i' を付けた拡張木を考え、その直径端点二つからの距離を比較する。
整数距離を最優先しつつ同距離では番号が大きい葉が遠くなり、通常の直径端点の性質をそのまま適用できる。
棄却する候補: 各頂点を始点に DFS/BFS して全頂点への距離と最大番号を求める。
正しいが全始点探索で O(N^2) となる。
頂点番号を tie-break とする距離比較で、任意頂点から最遠点 s、s から最遠点 t を求めて拡張木の直径端を得る。元の木で s,t から全距離を計算し、各 u について距離が大きい端、等しければ番号が大きい端を出力する。
典型の発動条件
木の直径
発動条件: 木の各頂点からの最遠点または離心率を一括して求めるとき。
直径端点 s,t からの二つの距離だけを比較して各頂点の最遠候補を決める。
微小摂動による tie-break
発動条件: 主目的値が同じ場合だけ副目的値を最大化したいとき。
葉への仮想的な微小辺、実装上は距離と番号の辞書順比較で最大番号条件を埋め込む。
問題固有の要素
最大番号という副条件も、十分小さい重みを加えた単一の距離最大化とみなせる。
別の問題へ持ち帰る視点: 木の直径端点の性質は、順序を壊さない微小摂動で tie-break を含む目的へ拡張できる。
正当性
各頂点へ番号×微小εの補助葉を付けると整数距離優先・番号後順位の最遠が一つの木距離最大化になる。拡張tree直径の二端が全最遠を代表する性質を使い、実装は距離/番号pair比較でεを正確に模倣する。両探索と回答に同tie規則を使えば最大番号を失わない。
実装上の注意
- 浮動小数 ε は実装せず、距離が同じ場合だけ頂点番号を比較する。直径探索と各頂点の回答の両方で同じ比較規則を使う。
復習の核
- 直径端点の探索でも同距離時の最大番号を選んでいるか、各 u の比較が距離優先・番号後順位になっているかを確認する。
計算量と制約
時間
N頂点、tie付き直径探索と二距離 O(N)、出力O(N)。
空間
木と二距離 O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 5 \times 10^5; 1 \leq A_i \lt B_i \leq N; The graph given in the input is a tree.; All input values are integers.
出典