yukicoder : No.2726 Rooted Tree Nim

こんなNimあったな…。
https://yukicoder.me/problems/no/2726

問題

根付き木が与えられる。
各点にはいくつかの石が置いてある。

ここで以下のルールのNimを行う。

• 正整数Kが与えられるので、自ターンのプレイヤーは根以外の石が1個以上ある頂点を選び、1～K個石を親頂点に動かす
• そのような選び方ができない側は負け。

最適手を取るときの勝者はどちらか。

解法

まず深さ偶数の点は無視してよい。
片方がいくつか石を動かした場合、相手がそれらの石をもう一度親頂点に動かすことができるためである。

よって、深さ奇数の点に対し、上限付きNimを解けばよい。

int T,N,K;
vector<int> E[202020];
int A[202020];

int dfs(int cur,int pre,int turn) {
	int ret=0;
	if(turn) ret^=A[cur]%(K+1);
	FORR(e,E[cur]) if(e!=pre) ret^=dfs(e,cur,turn^1);
	return ret;
}

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

まとめ

上限付きNimの解き方忘れてた…。