CODE THANKS FESTIVAL 2015 : F - お祭りとお菓子

結構迷ったけどコードは単純。
http://code-thanks-festival-2015-open.contest.atcoder.jp/tasks/code_thanks_festival_2015_f

問題

木を成す無向グラフが与えられる。
この木に対し、2人で交互にターンが来るゲームを行う。
両ターンでは、辺が１つしかない頂点を1つ選択し、その頂点と辺を取り除く、という処理を行う。
最後に頂点１を取り除いた方が勝ちである。

両者最適手を取った場合、勝者はどちらか。

解法

グラフを頂点１を根とする根付き木と見なす。
頂点１の次数が１なら、先手がそれを取り除いて勝利確定。

そうでないなら、頂点１の子頂点が1個の状態にできれば勝ちとなる。
今回の条件では、葉の頂点1個ずつしか頂点を削除できないので、頂点1の子頂点を削除するには結局その子頂点のsubtreeの頂点数のターンがかかる。

自分のターンで頂点１の子頂点が1個になると負けてしまうので、両者とも子頂点の最後の1個は取らないよう、subtreeの頂点数が2以上あるところから取ろうとするだろう。
そうすると結局頂点１以外の頂点数が奇数の状態に持ち込めれば勝ちとなる。
よって、初期状態で頂点数が偶数なら先手、奇数なら後手の勝ち。

int N;
int in[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		in[x]++;
		in[y]++;
	}
	
	if(in[1]<=1 || N%2==0) _P("A\n");
	else _P("B\n");
	
}

まとめ

本番無駄にSubtreeの頂点数数え上げDFSを書いてタイムロスした。