ABC 218 G — Game on Tree 2

考察

木を頂点1で根付けると、再訪禁止の駒は親へ戻れず子へ進み続け、必ず葉で止まる。終端の葉を固定すれば訪問集合は根からその葉までの path に一意に定まる。

各葉の path 中央値が分かれば、内部頂点では手番に応じて子の値の最大または最小を選ぶだけなので、ゲーム部分は通常の minimax 木 DP になる。

採用する候補: DFS 中の根から現在頂点までの値の multiset を二分割して中央値を保ち、葉の評価値を求めながら深さ偶数で max、奇数で min を返す。

path への一要素追加・削除と中央値取得を効率化し、葉の payoff 計算と minimax を一度の DFS に統合できる。

棄却する候補: 葉ごとに根からの値を集め直してソートし、その後ゲーム木を評価する。

多くの葉が長い共通 path を持つ木では同じ頂点値を繰り返し集計し、N=10^5 に対して二乗規模になり得る。

DFS の入場時に A_v を追加し、退場時に同じ一個を削除すれば、データ構造は常に現在の root-to-v path だけを表す。

根の深さを0とすると、次の行き先を選ぶのは偶数深さで Taro、奇数深さで Jiro なので、それぞれ子の返り値の max と min を取る。

値を座標圧縮した Fenwick Tree の k-th 探索、または大小二つの multiset で path 中央値を管理する。葉では奇数個なら中央、偶数個なら中央二値の平均を返し、内部では深さの偶奇で集約する。

典型の発動条件

DFS path データ構造

発動条件: 各 root-to-node path の統計量を全頂点または全葉で求め、要素の追加と rollback ができるとき。

DFS 入退場で一要素ずつ更新し、兄弟部分木へ path 状態を持ち越さない。

ゲーム木の minimax

発動条件: 完全情報ゲームが木上を一方向に進み、終端 payoff が決まるとき。

最大化手番では子値の最大、最小化手番では最小を bottom-up に返す。

問題固有の要素

再訪禁止と入力が木であることの組合せが、一般の walk ゲームを「葉を選ぶゲーム」へ変える。中央値は終端 path だけで決まり途中手番の履歴を別状態に持たない。

別の問題へ持ち帰る視点: グラフゲームで履歴依存に見えたら、木・非再訪・開始点から合法手が常に子方向だけになるかを先に確認する。

正当性

木では根から葉への経路が一意である。DFSの追加と取り消しがその経路の値を保つので、葉の評価は実際の中央値に一致する。各内部頂点で手番の最適な子を選べば、葉からの帰納により根の値がゲームの最適値となる。

実装上の注意

  • 重複値を一個ずつ削除できる構造にし、偶数長 path では中央二値の和を2で割る。A_i が偶数なので答えは整数だが、再帰深度 N の実装にも注意する。

復習の核

  • 根・内部・葉の三段の小木で、手番と深さの対応を書き込み、中央値の管理と max/min の向きを別々に再現する。

計算量と制約

時間

O(N log N)、path中央値と木minimax。

空間

O(N)、path頻度/木/DFS履歴。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 10^5; 2 \leq A_i \leq 10^9; A_i is even.; 1 \leq u_i < v_i \leq N; The given graph is a tree.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Game on Tree 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: rollback・DFS入退場の状態復元

主題
  • rollback・DFS入退場の状態復元: 更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • minimax・得点差・局面値を評価するゲームDP: 有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: rollback・DFS入退場の状態復元

    補助タグ: 有限局面DAGのminimax ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: rollback・DFS入退場の状態復元

    • 更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題