AtCoder AGC #014 : D - Black and White Tree

解けたのはいいけど手間取りすぎた。
http://agc014.contest.atcoder.jp/tasks/agc014_d

問題

木を成すグラフに対し、２人で行うゲームを考える。
両者交互に、未彩色の頂点を1つ選び先手は白、後手は黒で塗っていく。

すべての頂点に色が塗られたら、黒頂点に隣接する頂点を黒で上書きする、という処理を同時に行う。
この時、先手は白頂点が1つでも残るようにできるか。

解法

このグラフを二部グラフとみなした場合、完全マッチングが存在するなら後手必勝である。
先手の塗った頂点に対し、対応するマッチング先頂点を黒く塗ると、すべての白頂点が黒頂点に隣接し、最後の処理で黒に上書きされる。
逆にそうでなければ先手必勝である。

…ということで完全マッチングの有無を求めてもよいが、自分は別の手で行った。
葉に隣接した頂点を白く塗った場合、葉頂点も白く塗るとそこは処理の後も必ず白く残る。
逆に言えば、白頂点が残らないようにするには後手は次の手番でそこを塗るしかない。
こうして選んだ２頂点は、以後取り除いてもゲームに影響しない。
葉頂点の黒は隣の同時に取り除く白頂点を上書きするだけだし、白頂点は他に影響しない。

よって、葉頂点を見つけ次第、その頂点と隣接頂点(およびそれらにつながる辺)を取り除く、ということを繰り返そう。
途中、次数が0の頂点が生じた場合、そこを先手が白く塗ると後手は隣接点を取れないので先手が勝ちである。

int N;
set<int> E[101010];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	
	set<pair<int,int>> S;
	FOR(i,N) {
		S.insert({E[i].size(),i});
	}
	
	while(S.size()) {
		if(S.begin()->first==0) return _P("First\n");
		x = S.begin()->second;
		y = *E[x].begin();
		
		FORR(r,E[y]) {
			S.erase({E[r].size(),r});
			E[r].erase(y);
			S.insert({E[r].size(),r});
		}
		S.erase({E[y].size(),y});
		S.erase({E[x].size(),x});
	}
	_P("Second\n");
	
}

まとめ

妙に手間取った。