爱丽丝和鲍勃将通过玩一棵礼物树的游戏来庆祝圣诞节。该树有 $$$n$$$ 个节点(编号为 $$$1$$$ 到 $$$n$$$,其中某个节点 $$$r$$$ 作为其根)。第 $$$i$$$ 个节点上挂着 $$$a_i$$$ 礼物。
在开始游戏之前,选择一个特殊的整数$$$k$$$。游戏进行如下:
- Alice开始游戏,每回合交替移动;
- 在任何移动中,当前玩家都可以选择深度至少为 $$$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$$$,相应地,$$$a_j$$$增加了$$$m$$$;
- Alice 和 Bob 都发挥最佳。无法采取行动的玩家输掉游戏。
对于树的每个可能的根,找出 Alice 或 Bob 中谁赢得了游戏。
注意:以 $$$r$$$ 为根的树中节点 $$$i$$$ 的深度定义为从节点 $$$r$$$ 到节点 $$$i$$$ 的简单路径上的边数。根 $$$r$$$ 本身的深度为零。
输入
第一行包含两个空格分隔的整数 $$$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)$$$。
输出
输出 $$$n$$$ 整数,其中如果当树以节点 $$$i$$$ 为根时 Alice 赢得游戏,则第 $$$i$$$ 个整数为 $$$1$$$,否则为 $$$0$$$。
示例
输入 #1
5 1 1 2 1 3 5 2 4 3 0 3 2 4 4
输出 #1
1 0 0 1 1
注意
让我们计算根节点为 1 和 2 的样本输入的答案。
根节点1
在这种情况下,爱丽丝总是获胜。 Alice 和 Bob 之间的一种可能的游戏玩法是:
- Alice 将一件礼物从节点 4 移动到节点 3。
- Bob 将四份礼物从节点 5 移动到节点 2。
- Alice 将四件礼物从节点 2 移动到节点 1。
- Bob 将三个礼物从节点 2 移动到节点 1。
- Alice 将三件礼物从节点 3 移动到节点 1。
- Bob 将三个礼物从节点 4 移动到节点 3。
- Alice 将三件礼物从节点 3 移动到节点 1。
Bob 现在无法采取行动,因此失败了。
根节点2
在这种情况下,鲍勃总是获胜。其中一种游戏玩法是:
- Alice 将四份礼物从节点 4 移动到节点 3。
- Bob 将四份礼物从节点 5 移动到节点 2。
- Alice 将六件礼物从节点 3 移动到节点 1。
- Bob 将 6 个礼物从节点 1 移动到节点 2。
Alice 现在无法移动,因此失败。