yukicoder : No.2841 Leaf Eater

ありそうで見かけなかった問題。
https://yukicoder.me/problems/no/2841

問題

根付き木を使った2人対戦ターン制ゲームを行う。
各自のターンでは、葉である頂点を1個以上選び削除することができる。
そのような葉がない場合(=根頂点しか残っていない場合)は負けとなる。

木が与えられたとき、最適手を取ったときの勝者を答えよ。

解法

葉から、親をたどり子頂点が2個以上あるような点までの距離を考える。
その距離が奇数であるものが1個でもあれば先手の勝ちである。

先手は、そのような葉を削除すると、残された木はそのような葉が1個もない状態になるためである。

int T,N,P[202020],D[202020],C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) D[i]=C[i]=0;
		
		FOR(i,N-1) {
			cin>>x;
			P[i+1]=x-1;
			C[x-1]++;
		}
		
		int ok=0;
		for(i=1;i<N;i++) {
			D[i]=D[P[i]]+1;
			if(C[i]==0) {
				if(D[i]%2) ok=1;
			}
			else {
				if(C[i]>=2) D[i]=0;
			}
		}
		if(ok) cout<<"First"<<endl;
		else cout<<"Second"<<endl;
	}
	
}

まとめ

こういうターン制ゲーム、どうやって考察していけばいいのかいまいちコツがわからないんだよな。
いくらでも減らせる→Grundy数、1個減らせる→偶奇を疑う、以上になんか典型テクあるかな。