先来复习一下基本的Nim游戏:有堆石子,每次选择任意一堆拿走任意多个,不能走的人败。我们知道Nim游戏先手必胜的结论是每一堆个数的和不为0(证明可以自行搜索)。
那么我们考虑把这种Nim游戏推广到树上:一棵树,每个节点都有若干个石子,每次可以选择任意一个节点将任意多个石子移动到其父亲,不能走的人败。假设根节点的深度为0,我们可以发现,如果先手玩家希望把一个偶数深度的棋子移动到奇数深度,那么后手玩家可以将那些棋子再次移动到偶数深度,相当于撤销了先手的操作。
所以先手只有把奇数深度的棋子移动到偶数深度,才能实现先后手玩家互换。因为如果后手试图“撤销”先手的这部操作,将这些棋子再次移动到奇数深度。那么先手可以再次将他们移动到偶数深度。一直这样往复移动,最后一步操作是先手把棋子移动到根节点(深度为0),后手无法接着移动,就实现了先后手互换。
我们刚刚证明了从任何人将棋子从偶数深度拿到奇数深度的操作都对局面没有影响,所以我们可以忽略所有从偶数深度出发的棋子。因此偶数深度就变成了“垃圾桶”,只进不出。我们发现,当我们把每个奇数节点看作独立的一堆石子,这个游戏就转化成了普通的Nim游戏。即每次选择一堆石子,拿掉任意多个丢进垃圾桶,不能操作的人败。所以我们只需要计算所有奇数深度节点的石子个数异或和就能判断局面是否是先手必胜了。
对于这道题来说,因为他是把棋子移动到第个祖先,就相当于每个点向其第个祖先连了一条有向边,然后在新的树上做树上Nim游戏。我们可以计算出每个节点在新树上是多少层,就能得知他的石子数有没有对答案的贡献。
因为这个题要对每个根都计算,所以换根DP即可,复杂度。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=1e5+1000;
int dp[maxn][40];
int a[maxn];
int now[40],trans[40],tmp[40];
int n,k;
int ans[maxn];
int JK[maxn][40];
vi side[maxn];
void dfs1(int u,int fa){
dp[u][0]=a[u];
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
dfs1(v,u);
rep(i,0,2*k-1){
int nxt=(i+1)%(2*k);
dp[u][nxt]^=dp[v][i];
}
}
}
void dfs2(int u,int fa){
int tot=0;
rep(i,k,2*k-1)tot^=now[i];
if(tot)ans[u]=1;
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
memcpy(trans,now,sizeof(trans));
rep(j,0,2*k-1){
int nxt=(j+1)%(2*k);
trans[nxt]^=dp[v][j];
}
memset(tmp,0,sizeof(tmp));
rep(j,0,2*k-1){
int nxt=(j+1)%(2*k);
tmp[nxt]^=trans[j];
}
rep(j,0,2*k-1){
tmp[j]^=dp[v][j];
}
memcpy(JK[u],now,sizeof(JK[u]));
memcpy(now,tmp,sizeof(tmp));
dfs2(v,u);
memcpy(now,JK[u],sizeof(JK[u]));
}
}
int main(){
ios::sync_with_stdio(0);cin>>n>>k;
rep(i,1,n-1){
int u,v;cin>>u>>v;
side[u].pb(v);side[v].pb(u);
}
rep(i,1,n)cin>>a[i];
dfs1(1,0);memcpy(now,dp[1],sizeof(now));
dfs2(1,0);
rep(i,1,n)cout<<ans[i]<<' ';
return 0;
}