Christmas Game
将对k取余分为 0,1,2,3,4,……k-1组,各组相当于单独的一个游戏
如 heapth=x*k+y,它则在第x层。
对于层数为奇数的,进行取石子(因为到了偶数层,可以下模仿棋)
$dp[u][i][0/1]$表示以u为根的子树,模k余数为i,且k的倍数是偶/奇的异或和
我们不妨%2k,这样偶数的区间一定是[0,k-1],奇数的区间一定是[k,2k-1] (因为多了一个k)
所以是设$dp[u][i]$
$dp[u][i]=dp[v][i-1] $ (如果i为0,还要异或上a[u])
$f[v][i]=dp[v][i]+(f[u][i+1]-dp[v][i+2])$
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef pair<int,int> pii;
typedef long long ll;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif
const int N=100005,M=2*N;
int h[N],ne[M],e[M],idx;
int dp[N][43];
int f[N][43];
int a[N],k;
int ans[N];
void add(int x,int y)
{
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs1(int u,int fa)
{
dp[u][0]=a[u];
for(int i=h[u];~i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
dfs1(v,u);
for(int j=0;j<2*k;j++)
{
dp[u][j]^=dp[v][(j-1+2*k)%(2*k)];
}
}
}
void dfs2(int u,int fa)
{
for(int i=h[u];~i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
for(int j=0;j<2*k;j++)
{
f[v][j]=(f[u][(j-1+2*k)%(2*k)] ^ dp[v][(j-2+2*k)%(2*k)] ^ dp[v][j]);
}
dfs2(v,u);
}
}
int main()
{
int n;
scanf("%d%d",&n,&k);
memset(h,-1,sizeof h);
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,-1);
for(int i=0;i<2*k;i++) f[1][i]=dp[1][i];
dfs2(1,-1);
for(int i=1;i<=n;i++)
{
for(int j=k;j<2*k;j++)
{
ans[i]^=f[i][j];
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]==0) printf("0 ");
else printf("1 ");
}
}