C++(clang++ 11.0.1) 解法, 执行用时: 191ms, 内存消耗: 24852K, 提交时间: 2023-07-22 11:16:24

#include <bits/stdc++.h>
#define rep(i,a,b)for(int i = (a); i < (b); i++)
#define _for(i,a,b) for(int i = (a); i <= (b); i++)
using namespace std;
const int N = 1e5 + 10;
int dp[N][45], sg[N], a[N], n, k;
vector<int> g[N];
void dfs(int u, int fa)
{
    dp[u][0] = a[u];
    for(int v: g[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        rep(j, 0, k) dp[u][(j + 1) % k] ^= dp[v][j];
    }
}
void dfs2(int u, int fa)
{
    _for(i, k / 2, k - 1) sg[u] ^= dp[u][i];
    for(int v: g[u])
    {
        if(v == fa) continue;
        rep(j, 0, k) dp[u][(j + 1) % k] ^= dp[v][j];
        rep(j, 0, k) dp[v][(j + 1) % k] ^= dp[u][j];
        dfs2(v, u);
        rep(j, 0, k) dp[v][(j + 1) % k] ^= dp[u][j];
        rep(j, 0, k) dp[u][(j + 1) % k] ^= dp[v][j];
    }
}
int main()
{
    scanf("%d%d", &n, &k);
    k *= 2;
    _for(i, 1, n - 1)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    _for(i, 1, n) scanf("%d", &a[i]);

    dfs(1, 0);
    dfs2(1, 0);
    _for(i, 1, n) printf("%d ", sg[i] > 0);
}