AGC017D: Game on Tree

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";
}