CF1498F Christmas Game

Alice 和 Bob 打算通过玩一个礼物树的游戏来庆祝圣诞节。这棵树有 $n$ 个节点（编号为 $1$ 到 $n$，以某个节点 $r$ 作为根）。第 $i$ 个节点上挂着 $a_i$ 个礼物。 在游戏开始前，会选择一个特殊的整数 $k$。游戏规则如下： - Alice 先手，之后双方轮流行动； - 每一回合，当前玩家可以选择某个深度至少为 $k$ 的节点（比如 $i$），然后从该节点上取走任意正整数个礼物，记为 $m$（$1 \le m \le a_i$）； - 玩家将这 $m$ 个礼物放到节点 $i$ 的第 $k$ 级祖先（记为 $j$）上（节点 $i$ 的第 $k$ 级祖先是指 $i$ 是 $j$ 的后代，且 $j$ 的深度与 $i$ 的深度之差恰好为 $k$）。此时，第 $i$ 个节点的礼物数 $a_i$ 减少 $m$，第 $j$ 个节点的礼物数 $a_j$ 增加 $m$； - Alice 和 Bob 都会采取最优策略。无法进行操作的玩家判负。 对于每一个可能的树根，求出 Alice 和 Bob 谁会获胜。 注意：在以 $r$ 为根的树中，节点 $i$ 的深度定义为从根节点 $r$ 到节点 $i$ 的简单路径上的边数。根节点 $r$ 的深度为 $0$。

第一行包含两个用空格分隔的整数 $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$ 个整数表示当以第 $i$ 个节点为根时，Alice 是否能获胜。如果 Alice 获胜输出 $1$，否则输出 $0$。

我们以节点 $1$ 和节点 $2$ 分别作为根节点，计算样例输入的答案。 以节点 $1$ 为根时： Alice 总是能获胜。可能的游戏过程如下： - Alice 从节点 $4$ 移动一个礼物到节点 $3$。 - Bob 从节点 $5$ 移动四个礼物到节点 $2$。 - Alice 从节点 $2$ 移动四个礼物到节点 $1$。 - Bob 从节点 $2$ 移动三个礼物到节点 $1$。 - Alice 从节点 $3$ 移动三个礼物到节点 $1$。 - Bob 从节点 $4$ 移动三个礼物到节点 $3$。 - Alice 从节点 $3$ 移动三个礼物到节点 $1$。 此时 Bob 无法再进行操作，因此 Bob 输了。 以节点 $2$ 为根时： Bob 总是能获胜。可能的游戏过程如下： - Alice 从节点 $4$ 移动四个礼物到节点 $3$。 - Bob 从节点 $5$ 移动四个礼物到节点 $2$。 - Alice 从节点 $3$ 移动六个礼物到节点 $1$。 - Bob 从节点 $1$ 移动六个礼物到节点 $2$。 此时 Alice 无法再进行操作，因此 Alice 输了。 由 ChatGPT 4.1 翻译