ABC 428 E — Farthest Vertex

考察

木で任意頂点 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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Farthest Vertex の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 基準点からの木距離・剰余類・直径・中心

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 木距離・直径・中心・最遠点

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 基準点からの木距離・剰余類・直径・中心

      • 一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。

      この解説で扱わないこと:

      • 根付き木の子状態を合成する木DP、およびLCA・HLDによるパスの区間分解。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題