結構迷ったけどコードは単純。
http://code-thanks-festival-2015-open.contest.atcoder.jp/tasks/code_thanks_festival_2015_f
問題
木を成す無向グラフが与えられる。
この木に対し、2人で交互にターンが来るゲームを行う。
両ターンでは、辺が1つしかない頂点を1つ選択し、その頂点と辺を取り除く、という処理を行う。
最後に頂点1を取り除いた方が勝ちである。
両者最適手を取った場合、勝者はどちらか。
解法
グラフを頂点1を根とする根付き木と見なす。
頂点1の次数が1なら、先手がそれを取り除いて勝利確定。
そうでないなら、頂点1の子頂点が1個の状態にできれば勝ちとなる。
今回の条件では、葉の頂点1個ずつしか頂点を削除できないので、頂点1の子頂点を削除するには結局その子頂点のsubtreeの頂点数のターンがかかる。
自分のターンで頂点1の子頂点が1個になると負けてしまうので、両者とも子頂点の最後の1個は取らないよう、subtreeの頂点数が2以上あるところから取ろうとするだろう。
そうすると結局頂点1以外の頂点数が奇数の状態に持ち込めれば勝ちとなる。
よって、初期状態で頂点数が偶数なら先手、奇数なら後手の勝ち。
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を書いてタイムロスした。