Alice 和 Bob 在一棵 个点的树上玩游戏,第 个节点上有 个石子,每轮可以选择一个深度至少为 的节点并移动任意多石子到其 级祖先处,对每个结点询问如果将其作为根谁会赢。
。
首先不难发现 相当于拆成了多棵树,那么考虑 时一些特殊情况下先手必胜的条件:
- 菊花:此时是经典的 Nim 游戏,先手必胜当且仅当 ;
- 链(其实就是阶梯 Nim 游戏):把节点按照深度的奇偶性分成两类(根节点深度为 ),深度为奇数的叫奇节点,深度为偶数的叫偶节点。那么对偶节点进行操作是没用的,因为后手可以模仿先手的操作,把先手移去奇节点的石子都往前移到下一个偶节点,最后移到无法移动的根节点,先手还是先手。所以可以把在奇节点上的操作看作是丢掉了一些石子,那么先手必胜当且仅当 ;
考虑将链的情况推广一下,不难发现,对于任意一棵树,链情况的结论都成立。所以 时先手必胜当且仅当 。
对于 的情况,拆成多棵 的树做,先手必胜当且仅当 。
简单换根 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;
}