ABC 246 G — Game on Tree 3

考察

得点 X 以上を保証できるかだけを見ると、各非根頂点は A_i≥X の黒と A_i<X の白の 2 値に置き換えられる。判定は X に対して単調なので最大の真を探せる。

青木は各移動の直前に任意の 1 頂点を黒から白へできる。高橋がどの子を選んでも勝てない状態にするには、全子部分木で必要な事前削除数を合算する必要がある。

採用する候補: X を二分探索し、各 X で『青木が事前に何個黒頂点を白くすれば部分木から必勝か』を表す木 DP を行う。

履歴全体を持たず、青木の削除余力を頂点ごとの最小必要個数へ集約して単調判定できる。

棄却する候補: 盤面の黒白配置と現在頂点を状態にして、両者の全選択を minimax 探索する。

各手で任意頂点を 0 にできるため配置状態が指数個あり、N≤2×10^5 では扱えない。

dp[v] を、v から開始する前に青木が追加で白くすべき黒頂点の最小数とする。子の必要数の合計から、直後の青木の 1 回分を引ける。

B_v=1 if v is black else 0 とすると dp[v]=max(Σdp[c]-1,0)+B_v である。root は値を持たず白として扱い、dp[1]>0 なら青木の通常の 1 回/turn だけでは防げず高橋が X 以上を保証する。

候補 X ごとに A_i≥X を黒とし、postorder で dp を計算する。dp[root]>0 を判定の真として、真となる最大 X を値域または A_i の候補列上で二分探索する。

典型の発動条件

答え二分探索

発動条件: 『答えが X 以上か』が X に関して単調で、各閾値を十分速く判定できるとき。

頂点値を X 以上/未満へ二値化し、木 DP の勝敗判定が真となる最大 X を探す。

ゲームの資源量を表す木 DP

発動条件: 木上ゲームで全履歴は大きいが、相手が勝つための最小追加操作数が部分木ごとに合成できるとき。

各子の必要白塗り数を合計し、現在 turn にできる 1 回を差し引いて親へ返す。

問題固有の要素

任意頂点を毎 turn 1 個消せるという全域操作を、各部分木を無力化するための最小『前借り削除数』に置き換えると局所漸化式になる。

別の問題へ持ち帰る視点: ゲーム DP では勝敗だけで閉じない場合、勝敗を反転させるために必要な最小資源量を状態にすると合成可能になることがある。

正当性

子ごとの必要数は異なる部分木に属するので加算できる。青木の直後の一手でその合計を一つ減らせるが、黒いvで即座に止まる選択肢は別に塞ぐ必要がある。この二点が漸化式を与え、葉からの帰納で根の判定も正しい。

実装上の注意

  • root には A_1 がないので B_1=0 とし、判定の真偽は dp[1]>0 が高橋勝ち、dp[1]=0 が青木勝ちである。
  • 鎖状木で再帰深度が N になり得るため、反復 DFS の親・順序配列から逆順計算する実装も検討する。

復習の核

  • 葉の黒/白で dp が 1/0 になることから始め、分岐頂点で子 dp の合計からなぜ 1 だけ引けるかをゲームの手順に沿って説明させる。

計算量と制約

時間

O(N log V)、Vは値域幅または候補値数、判定postorder O(N)。

空間

O(N)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 単調境界を証明して探索する

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

    主タグ: 単調境界探索

    補助タグ: 根付き木DP・部分木集約

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

    学習の位置

    体系上の位置: 単調境界を証明して探索する

    • 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。

    先に読む単元:

    • 根付き木DP・部分木集約 — DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。

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

    • 連続窓の両端を一方向に進める尺取り法、および真偽判定の単調境界を持たない三分探索・局所探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題