Christmas Game
Description
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.
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)$.
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.
Input
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)$.
Output
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.
Samples
5 1
1 2
1 3
5 2
4 3
0 3 2 4 4
1 0 0 1 1
Note
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.