AtCoder AGC #017 : D - Game on Tree

知識ゲー？
http://agc017.contest.atcoder.jp/tasks/agc017_d

問題

根付き木を用いた2人のターン制ゲームを行う。
自分のターンでは、任意の辺を選択し根ではない方を切り落とす。
自分のターン開始時点で辺が残っていない方が負けとする。

互いに最適手を取るとき勝者は先手後手どちらか。

解法

Green Hackenbushとかいう有名問題らしい？

以下の手順で各頂点vのGrundy数G(v)を考えていき、根のGrundy数が非0なら先手の勝ち。

• 子頂点がない場合G(v)=0
• 子頂点がある場合、各子頂点v'に対し(G(v')+1)のxorを取ったものがG(v)

子頂点が1個の時、G(v)=G(v')+1となることを再帰的に示す。
子頂点のGrundy数がG(v')なので、子頂点のSubTreeの辺を切ることで子頂点のSubTreeのGrundy数を0～(G(v')-1)の任意の値にできるはずである。
これは言い換えれば元頂点vに対し、G(v)から1～G(v')のいずれにも遷移できるということを意味する。
また、子頂点までの辺を切ればG(v)から0に遷移できる。
結局G(v)から0～G(v')のいずれにも遷移できるのでG(v)=G(v')+1。

int N;
vector<int> E[101010];
int mex[101010];


int dfs(int cur,int pre) {
	
	FORR(e,E[cur]) if(e!=pre) mex[cur]^=dfs(e,cur)+1;
	return mex[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	if(dfs(0,-1)) cout<<"Alice"<<endl;
	else cout<<"Bob"<<endl;
	
	
}

まとめ

そんなん知らんよ…。