Game on Tree [AtCoder Grand Contest 017 D]

http://agc017.contest.atcoder.jp/tasks/agc017_d

前提知識

• Grundy数に関する知識

解説

http://agc017.contest.atcoder.jp/submissions/1413404

この解説は個人的な解釈であり、正当性は分からないです(合ってても間違ってても教えてほしい)

Grundy数を計算して勝敗を決するのは明らか(Nimにとても似てる)。
そして、辺を削除していくのではなく、頂点とその部分木を削除していくと解釈して進めていく。

自分のGrundy数とNimに対する解釈

• 得られたGrundy数はNimにおける石の個数となる
• ある2つのGrundy数のxorを取ることは、2つの石の山をマージして1つの石の山にしてしまうこと

ある頂点のGrundy数を計算するときに、
1. その頂点の子供のGrundy数を再帰的に求めてxorする（子供の石の山をマージして1つの石の山にする）
2. その答えに+1したものが、その頂点のGrundy数（マージしてできた石の山に石を1つ追加する）

これを再帰的に求めて、頂点1のGrundy数を見れば答え。
ただし、頂点1は取れないので、頂点1のGrundy数の計算の2番目は省略する（下の解法では1引くことで相殺してる）

int N;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
int dfs(int cu, int pa = -1) {
    int g = 0;
    for (int to : E[cu]) if (to != pa) g ^= dfs(to, cu);
    return g + 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    int g = dfs(1) - 1;

    if (g == 0) printf("Bob\n");
    else printf("Alice\n");
}