CF1498F Christmas Game 做题记录

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

n105,k20,ai109n\le 10^5 , k\le 20 , a_i\le 10^9

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

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

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

对于 k>1k>1 的情况,拆成多棵 k=1k=1 的树做,先手必胜当且仅当 itreedepi,u1(mod2)ai,u=0\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;
}