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:
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.
5 1 1 2 1 3 5 2 4 3 0 3 2 4 4
1 0 0 1 1
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:
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 is now unable to make a move and hence loses.
Name |
---|