CF1498F Christmas Game 做题记录

Alice 和 Bob 在一棵 $n$ 个点的树上玩游戏，第 $i$ 个节点上有 $a_i$ 个石子，每轮可以选择一个深度至少为 $k$ 的节点并移动任意多石子到其 $k$ 级祖先处，对每个结点询问如果将其作为根谁会赢。

$n\le 10^5 , k\le 20 , a_i\le 10^9$。

首先不难发现 $k>1$ 相当于拆成了多棵树，那么考虑 $k=1$ 时一些特殊情况下先手必胜的条件：

• 菊花：此时是经典的 Nim 游戏，先手必胜当且仅当 $\oplus_{u\not=root}a_u\not=0$；
• 链（其实就是阶梯 Nim 游戏）：把节点按照深度的奇偶性分成两类（根节点深度为 $0$），深度为奇数的叫奇节点，深度为偶数的叫偶节点。那么对偶节点进行操作是没用的，因为后手可以模仿先手的操作，把先手移去奇节点的石子都往前移到下一个偶节点，最后移到无法移动的根节点，先手还是先手。所以可以把在奇节点上的操作看作是丢掉了一些石子，那么先手必胜当且仅当 $\oplus_{dep_u\equiv 1\pmod 2}a_u\not=0$；

考虑将链的情况推广一下，不难发现，对于任意一棵树，链情况的结论都成立。所以 $k=1$ 时先手必胜当且仅当 $\oplus_{dep_u\equiv 1\pmod 2}a_u\not=0$。

对于 $k>1$ 的情况，拆成多棵 $k=1$ 的树做，先手必胜当且仅当 $\oplus_{i\in tree}\oplus_{dep_{i,u}\equiv 1\pmod 2}a_{i,u}\not=0$。

简单换根 dp 即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=200005;

int n,k;
int a[S];
int esum,to[S],nxt[S],h[S];
int dp[S][25][2],pd[S][25][2],ans[S];

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

void dfs1(int u,int fa)
{
	dp[u][0][1]=a[u];
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs1(v,u);
		dp[u][0][0]^=dp[v][k-1][1];
		dp[u][0][1]^=dp[v][k-1][0];
		for(int j=1;j<k;j++)
		{
			dp[u][j][0]^=dp[v][j-1][0];
			dp[u][j][1]^=dp[v][j-1][1];
		}
	}
}

void dfs2(int u,int fa)
{
	if(u==1)
	{
		for(int i=0;i<k;i++) pd[u][i][0]=dp[u][i][0],pd[u][i][1]=dp[u][i][1];
	}
	else
	{
		pd[u][0][0]=pd[fa][k-1][1]^dp[u][(k-2+k)%k][k==1?0:1];
		pd[u][0][1]=pd[fa][k-1][0]^dp[u][(k-2+k)%k][k==1?1:0];
		for(int i=1;i<k;i++)
		{
			pd[u][i][0]^=pd[fa][i-1][0]^dp[u][(i-2+k)%k][i==1?1:0];
			pd[u][i][1]^=pd[fa][i-1][1]^dp[u][(i-2+k)%k][i==1?0:1];
		}
		for(int i=0;i<k;i++) pd[u][i][0]^=dp[u][i][0],pd[u][i][1]^=dp[u][i][1];
	}
	for(int i=0;i<k;i++) ans[u]^=pd[u][i][0];
//	printf("%d %d\n",pd[u][0][0],pd[u][0][1]);
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs2(v,u);
	}
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs1(1,0),dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]==0?0:1);
	printf("\n");
	return 0;
}