Day 158-Q2 — 緑のハッケンブッシュ（Green Hackenbush）on 森 ＋ 勝ちとなる初手の全列挙

2026-09-23 赤色 Master / Phase 8+ ★★★★★★★★★ 組合せゲーム理論・Colon Principle・「必要なGrundy値」の根からの伝播

問題

地面（頂点 $0$）と頂点 $1, \dots, N$ からなる 根付き森 がある。頂点 $v$ ($1 \le v \le N$) は辺で親 $p_v$ ($0 \le p_v < v$) とつながっている（$p_v=0$ なら地面に直接生えている）。辺 $v$ とは「$v$ と $p_v$ を結ぶ辺」のこととする。

先手と後手が交互に、残っている辺を1本選んで切る。切った結果 地面とつながらなくなった部分はすべて消える。辺を切れなくなった人の負け（正規形）。

  1. 両者最善を尽くしたとき、先手が勝つなら First、後手が勝つなら Second を出力せよ。
  2. さらに、先手が最初に切ると勝てる辺 の番号をすべて昇順に出力せよ（先手必敗なら空行）。

入力形式

N
p_1 p_2 ... p_N

制約

#条件
1$1 \le N \le 2 \times 10^5$
2$0 \le p_v < v$

入出力例

入力例1

5
0 1 1 0 4

出力例1

First
2 3 5

（頂点1の下に2,3、頂点4の下に5。Grundy値は3。辺2・辺3・辺5のどれを切っても残りのGrundy値が0になる）

問1 は AtCoder AGC017 D「Game on Tree」（https://atcoder.jp/contests/agc017/tasks/agc017_d 、2026-09-23 参照）と同じ構造（そちらは木1本・根を地面とみなす）。問2（勝ち手の全列挙を $O(N)$ で）は本シリーズ用に追加した拡張。

概念図：森とGrundy値・勝ち手

入力例1 の森（黄色の辺 = 先手の勝ち手）地面（頂点 0）辺1辺2辺3辺4辺51g=02g=03g=04g=15g=0寄与 g(1)+1 = 1寄与 g(4)+1 = 2g(0) = 1 ⊕ 2 = 3 ≠ 0→ First

ヒント（クリックで段階的に開示）

ヒント1（方向性）

地面に生えた木が複数ある = 独立なゲームの和。Sprague–Grundy の定理で「各木の Grundy 値の XOR」が 0 かどうかで勝敗が決まる。問題は 1本の木の Grundy 値 をどう求めるか。

ヒント2（アプローチ）

Colon Principle（コロン原理）: 頂点 $u$ から生えている部分木たち（竹の束）は、その XOR と同じ Grundy 値を持つ 1本の竹 に置き換えてもゲームの値が変わらない。長さ $k$ の竹（一直線の辺 $k$ 本）の Grundy 値は $k$。よって「子 $c$ の部分木に辺 $(u,c)$ を1本足したもの」は Grundy 値 $g(c)+1$ を持ち、

$$g(u) = \bigoplus_{c \in \mathrm{child}(u)} \bigl(g(c) + 1\bigr)$$

ヒント3（誘導）

問2 は全辺について「切った後の $g(0)$」を求めると $O(N \cdot \text{深さ})$ になる。代わりに 根から「この頂点の Grundy 値が何になれば全体が 0 になるか」= need(v) を配る。

  • $need(0) = 0$
  • 辺 $c$ を切る: 親 $u$ の値が $g(u) \oplus (g(c)+1)$ になる → これが $need(u)$ と等しければ勝ち手
  • $c$ より下の辺を切る: $g'(c)+1 = need(u) \oplus g(u) \oplus (g(c)+1)$ が必要 → $need(c) = $ その値 $-1$（その値が $0$ なら $g'(c)+1 \ge 1$ なので不可能）

模範解答 (Python)

模範解答を表示する（まず自力で解いてから） 
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    par = [0] + [int(x) for x in data[1:1 + n]]
    children = [[] for _ in range(n + 1)]
    for v in range(1, n + 1):
        children[par[v]].append(v)

    # p_v < v なので番号の降順に処理すれば子→親の順になる（再帰不要）
    g = [0] * (n + 1)
    for v in range(n, 0, -1):
        g[par[v]] ^= g[v] + 1

    # need[v] : 部分木 v の Grundy 値がこれになれば全体が 0 になる（-1 は不可能）
    need = [-1] * (n + 1)
    need[0] = 0
    win = []
    for u in range(0, n + 1):          # 番号の昇順 = 親→子の順
        if need[u] < 0:
            continue
        gu = g[u]
        for c in children[u]:
            contrib = g[c] + 1
            if gu ^ contrib == need[u]:  # 辺 c を切る
                win.append(c)
            t = need[u] ^ gu ^ contrib   # c より下を切るとき g'(c)+1 が満たすべき値
            need[c] = t - 1 if t >= 1 else -1

    print("First" if g[0] != 0 else "Second")
    print(" ".join(map(str, sorted(win))))


main()

計算量: $O(N)$（ソートを含めて $O(N \log N)$、勝ち手は親→子の順に見つかるので実際にはほぼ整列済み）。

Step-by-Step 解説

1竹（一直線）は Nim の山と同じ

長さ $k$ の竹から辺を1本切ると、そこより上は消えるので長さ $0..k-1$ のどれにでもなれる。これは石 $k$ 個の Nim の山と完全に同じで、Grundy 値は $k$。

2Colon Principle で木を竹に畳む

頂点 $u$ に子の枝が複数ぶら下がっているとき、それらは「$u$ を共有した独立なゲームの和」。Colon Principle（Berlekamp–Conway–Guy『Winning Ways』第7章）は、同じ Grundy 値を持つ枝同士はその場で交換してもゲーム全体の値が変わらない ことを保証する。したがって子の寄与 $g(c)+1$（子の部分木を竹に畳んだ長さ ＋ 辺 $(u,c)$ の1本）の XOR が $u$ の値になる。

3入力例1を手で追う
  • $g(2)=g(3)=g(5)=0$（葉）
  • $g(1) = (0+1)\oplus(0+1) = 0$、$g(4) = 0+1 = 1$
  • $g(0) = (g(1)+1)\oplus(g(4)+1) = 1 \oplus 2 = 3 \ne 0$ → First
4勝ち手を $O(N)$ で列挙（need の伝播）

辺を1本切ると、変わるのは その辺から根までのパス上の Grundy 値だけ。根から見て「この頂点がいくつになってくれれば全体が 0 か」を逆算して配ると、各辺の判定は $O(1)$ になる。入力例1では

  • $need(0)=0$。辺1: $3 \oplus 1 = 2 \ne 0$ ✗、辺4: $3 \oplus 2 = 1 \ne 0$ ✗
  • $need(1) = (0 \oplus 3 \oplus 1) - 1 = 1$。辺2: $g(1) \oplus 1 = 1 = need(1)$ ✓、辺3 も同様 ✓
  • $need(4) = (0 \oplus 3 \oplus 2) - 1 = 0$。辺5: $g(4) \oplus 1 = 0 = need(4)$ ✓
5なぜ $t=0$ なら不可能なのか

部分木 $c$ の中で何を切っても辺 $(u,c)$ は残るので、寄与は $g'(c)+1 \ge 1$。必要な寄与 $t$ が $0$ なら到達不能。これを見落として $need(c)=-1$ を「値 $-1$」として XOR に使うと、Python では負数の XOR が通ってしまい静かに誤答する。

迷った他案と採らなかった理由

案計算量採否理由
全状態のゲーム木探索（辺集合のビットマスクでメモ化）$O(2^N \cdot N^2)$検証用のみ正しさの基準として $N \le 11$ で使用。本番制約では不可能
各辺を切ったあと根まで Grundy 値を再計算$O(N \cdot \text{深さ})$不採用1本道（パスグラフ）で $O(N^2)=4\times10^{10}$。ランダム木なら通るが最悪ケースを落とす
全方位木DP（rerooting）で各辺の「切断後の値」を求める$O(N)$不採用本問で変わるのは根までのパスだけで、根を動かす必要はない。need の一方向伝播の方が単純で誤りにくい
need の根からの伝播（本解）$O(N)$採用1回のボトムアップ＋1回のトップダウン。判定は XOR 1回

前提が変わったら: 辺に色がある（青・赤＝ Blue-Red Hackenbush）と Grundy 値ではなく Conway の数（surreal number） で評価する別理論になり、本解はそのままでは使えない。閉路を含むグラフ（一般の Green Hackenbush）では Fusion Principle（閉路を地面側に縮約してループに置き換える）が必要で、本問は森に限定した。

よくあるミス

ミス原因正しい書き方
$g(u) = \bigoplus g(c)$ と書く（+1 忘れ）辺 $(u,c)$ 自体も1本の辺としてゲームに含まれることを忘れる子の寄与は $g(c)+1$
$g(u) = 1 + \bigoplus g(c)$ と書く「+1」の位置を XOR の外に出す+1 は 各子ごと、XOR の内側
深い木で再帰 DFS が RecursionError$N=2\times10^5$ のパス$p_v < v$ を使い番号の降順ループ（本解）か、明示スタック
need が不可能（$t=0$）の場合を $-1$ のまま XOR に使う「不可能」を値と混同need[u] < 0 なら子孫を全部スキップ
勝ち手を「$g(c)+1 = g(0)$ の辺」とだけ判定地面直下の辺しか見ていない深い辺を切ると祖先すべての値が変わる。need 伝播で全辺を判定

次のステップ

  • 発展1: Fusion Principle を実装して、閉路を含む一般グラフの Green Hackenbush の Grundy 値を求める（二重辺連結成分を縮約 → 各成分の辺数の偶奇でループ数が決まる）
  • 発展2: Blue-Red Hackenbush の竹の値（2進小数）を計算し、「Grundy 値が使えないゲーム」がどう評価されるかを体験する
  • 扱わなかった範囲: 誤規形（misère、最後に取った人が負け）。Hackenbush の misère 版は Grundy 値だけでは決まらない

検証ログ（本セッションで実行した数値）

  • 入力例1: 本解 (g=3, 勝ち手=[2,3,5])、全状態探索 (g=3, 勝ち手=[2,3,5]) で一致
  • ランダムテスト: $N \le 11$ の森（各頂点 15% で地面直結）400 件で、Grundy 値と勝ち手の集合の両方を全状態探索（辺集合ビットマスク＋メモ化）と比較 → 不一致 0 件
  • 模範解答そのもの（標準入力版・降順ループ版）でも、ランダム 100 件（$N\le10$）を全状態探索と比較 → 不一致 0 件
  • 性能（実測）: $N=2\times10^5$、$p_v \in [v-3, v-1]$ の細長い森で 0.064 秒（$g(0)=100010$、勝ち手 1 本）。深さが大きいので「根まで再計算」案では最悪に近い形
  • 検証スクリプト: スクラッチパッドの q2.py（上記は実行結果の転記）

自己評価

自分の回答

気づき・メモ