CF1498F.Christmas Game

Alice and Bob are going to celebrate Christmas by playing a game with a tree of presents. The tree has $n$ nodes (numbered $1$ to $n$, with some node $r$ as its root). There are $a_i$ presents are hanging from the $i$-th node.

Before beginning the game, a special integer $k$ is chosen. The game proceeds as follows:

• Alice begins the game, with moves alternating each turn;
• in any move, the current player may choose some node (for example, $i$) which has depth at least $k$. Then, the player picks some positive number of presents hanging from that node, let's call it $m$ $(1 \le m \le a_i)$;
• the player then places these $m$ presents on the $k$-th ancestor (let's call it $j$) of the $i$-th node (the $k$-th ancestor of vertex $i$ is a vertex $j$ such that $i$ is a descendant of $j$, and the difference between the depth of $j$ and the depth of $i$ is exactly $k$). Now, the number of presents of the $i$-th node $(a_i)$ is decreased by $m$, and, correspondingly, $a_j$ is increased by $m$;
• Alice and Bob both play optimally. The player unable to make a move loses the game.

For each possible root of the tree, find who among Alice or Bob wins the game.

Note: The depth of a node $i$ in a tree with root $r$ is defined as the number of edges on the simple path from node $r$ to node $i$. The depth of root $r$ itself is zero.

爱丽丝和鲍勃将通过在一棵礼物树上玩游戏来庆祝圣诞节。这棵树有 $n$ 个节点（编号为 $1$ 到 $n$，其中某个节点 $r$ 作为根节点）。第 $i$ 个节点上悬挂着 $a_i$ 件礼物。

游戏开始前，先选定一个特殊的整数 $k$。游戏规则如下：

• 爱丽丝先手，之后双方轮流进行操作；
• 在每次操作中，当前玩家可选择一个深度至少为 $k$ 的节点（例如节点 $i$），然后从中取走若干件礼物（设为 $m$ 件，满足 $1 \le m \le a_i$）；
• 接着，该玩家将这 $m$ 件礼物移动到节点 $i$ 的第 $k$ 级祖先节点（记为 $j$）上（节点 $i$ 的第 $k$ 级祖先 $j$ 是指：$i$ 是 $j$ 的后代，且 $j$ 与 $i$ 的深度之差恰好为 $k$）。此时，节点 $i$ 上的礼物数 $a_i$ 减少 $m$，而节点 $j$ 上的礼物数 $a_j$ 增加 $m$；
• 爱丽丝与鲍勃均以最优策略进行游戏。无法进行合法操作的一方判负。

对树的每一种可能的根节点（即对每个 $r = 1, 2, \dots, n$），判断爱丽丝与鲍勃中谁获胜。

注：在以 $r$ 为根的树中，节点 $i$ 的深度定义为从根节点 $r$ 到节点 $i$ 的简单路径上的边数；根节点 $r$ 自身的深度为 $0$。

The first line contains two space-separated integers $n$ and $k$ $(3 \le n \le 10^5, 1 \le k \le 20)$.

The next $n-1$ lines each contain two integers $x$ and $y$ $(1 \le x, y \le n, x \neq y)$, denoting an undirected edge between the two nodes $x$ and $y$. These edges form a tree of $n$ nodes.

The next line contains $n$ space-separated integers denoting the array $a$ $(0 \le a_i \le 10^9)$.

第一行包含两个以空格分隔的整数 $n$ 和 $k$ $(3 \le n \le 10^5, 1 \le k \le 20)$。

接下来的 $n-1$ 行每行包含两个整数 $x$ 和 $y$ $(1 \le x, y \le n, x \neq y)$，表示节点 $x$ 与节点 $y$ 之间的一条无向边。这些边构成一棵含 $n$ 个节点的树。

下一行包含 $n$ 个以空格分隔的整数，表示数组 $a$ $(0 \le a_i \le 10^9)$。

Output $n$ integers, where the $i$-th integer is $1$ if Alice wins the game when the tree is rooted at node $i$, or $0$ otherwise.

输出 $n$ 个整数，其中第 $i$ 个整数为 $1$ 表示当树以节点 $i$ 为根时 Alice 获胜，否则为 $0$。

Let us calculate the answer for sample input with root node as 1 and as 2.

Root node 1

Alice always wins in this case. One possible gameplay between Alice and Bob is:

• Alice moves one present from node 4 to node 3.
• Bob moves four presents from node 5 to node 2.
• Alice moves four presents from node 2 to node 1.
• Bob moves three presents from node 2 to node 1.
• Alice moves three presents from node 3 to node 1.
• Bob moves three presents from node 4 to node 3.
• Alice moves three presents from node 3 to node 1.

Bob is now unable to make a move and hence loses.

Root node 2

Bob always wins in this case. One such gameplay is:

• Alice moves four presents from node 4 to node 3.
• Bob moves four presents from node 5 to node 2.
• Alice moves six presents from node 3 to node 1.
• Bob moves six presents from node 1 to node 2.

Alice is now unable to make a move and hence loses.

我们来计算样例输入中以节点 1 和节点 2 分别为根节点时的答案。

根节点为 1

此时 Alice 总是获胜。Alice 与 Bob 之间的一种可能对局如下：

• Alice 将 1 个礼物从节点 4 移动到节点 3。
• Bob 将 4 个礼物从节点 5 移动到节点 2。
• Alice 将 4 个礼物从节点 2 移动到节点 1。
• Bob 将 3 个礼物从节点 2 移动到节点 1。
• Alice 将 3 个礼物从节点 3 移动到节点 1。
• Bob 将 3 个礼物从节点 4 移动到节点 3。
• Alice 将 3 个礼物从节点 3 移动到节点 1。

此时 Bob 无法进行任何操作，因此失败。

根节点为 2

此时 Bob 总是获胜。其中一种可能对局如下：

• Alice 将 4 个礼物从节点 4 移动到节点 3。
• Bob 将 4 个礼物从节点 5 移动到节点 2。
• Alice 将 6 个礼物从节点 3 移动到节点 1。
• Bob 将 6 个礼物从节点 1 移动到节点 2。

此时 Alice 无法进行任何操作，因此失败。