Codeforces #711 Div2 : F. Christmas Game

本番はEよりすんなり解いてるなぁ。
https://codeforces.com/contest/1498/problem/F

問題

木を成す無向グラフが与えられる。
各頂点には非負整数A[i]が設定されている。

根頂点を1つ定め、2人で以下のターン制ゲームを行う。

• 深さK以上の頂点vのうちA[v]が正のものを1つ選び、A[v]の値を減らしてK世代親頂点にその分値を足す

操作ができなくなった方の負けである。

各頂点を根としたとき、それぞれ勝者はどちらか。

解法

f(d) := 深さdである頂点vにおけるA[v]のxorを取った値
とすると、f((2n+1)K+m) (nは非負整数、mはK未満の非負整数)のxorを取った値が正なら先手の勝ちである。
そこで、f(d mod 2K)の値のxorをそれぞれ、全方位木DPの要領で求めて行けばよい。

どの頂点も深さが2K未満の場合、この問題は深さK～(2K-1)にある頂点vの値A[v]に関するnimになる。
もし深さ2K以上の場合も、(2n+1)K+mの深さにある頂点の値をいずれかがl動かしたとき、その相手は対応して(2n)K+mの深さにある頂点の値をlだけ(2n-1)K+mに動かせば元と同じ状態になるので、結局深さの値をmod 2Kして考えればよいことになる。

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

ll dp[202020][40];

void dfs(int cur,int pre) {
	dp[cur][0]^=A[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		int i;
		FOR(i,2*K) dp[cur][(i+1)%(2*K)]^=dp[e][i];
	}
}

void dfs2(int cur,int pre,vector<int> V) {
	int i;
	FOR(i,2*K) dp[cur][(i+1)%(2*K)]^=V[i];
	FORR(e,E[cur]) if(e!=pre) {
		FOR(i,2*K) V[i]=dp[cur][i]^dp[e][(i+2*K-1)%(2*K)];
		dfs2(e,cur,V);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	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];
	dfs(0,0);
	vector<int> V(2*K);
	dfs2(0,0,V);
	
	FOR(i,N) {
		int nim=0;
		FOR(j,K) nim^=dp[i][j+K];
		cout<<(nim>0)<<" ";
	}
	cout<<endl;
	
}

まとめ

よく本番すんなり思いつけたな。