http://agc017.contest.atcoder.jp/tasks/agc017_d
(ある点vのsubtree)と(vから親pへ向かう辺)で構成されるグラフについてgrundyが求まれば、あとはXORをとれば、pのsubtreeに対してgrundy(p)が求まります。grundy(v)は再帰的に求まるとして、このグラフにvからpへ向かう辺が追加されたとき、grundy数は何になるかが問題になります。
おそらくgrundy(v)+1になることが予想されるので、grundy数についての帰納法で解けばええやん!と思いましたがこれは無理です。
grundy数に対して帰納法は適応できないということです。
grundy(v)=0..k-1まで示せているとしてgrundy(v)=kを考えてみましょう。するとsubtree+1辺のグラフから1辺取り除いた時、grundy数がkよりも大きい値をとる可能性があります。kよりも大きいgrundy数は仮定にないので失敗となります。
なので頂点に対して帰納法をしましょう。すると簡単に示せます。
木は構成要素が多くて、注目するものを間違うとスムーズに解けないことを再確認しました。
int N; vector<int> G[MAX_N]; int dfs(int v, int p = -1) { int res = 0; rep(i, 0, G[v].size()) { int n = G[v][i]; if(n == p) continue; res ^= (dfs(n, v) + 1); } return res; } void solve() { cin >> N; rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } if(dfs(0)) cout << "Alice\n"; else cout << "Bob\n"; }