Christmas Game

题意翻译

Alice 和 Bob 在一棵 $n$ 个点的树上玩游戏，第 $i$ 个节点上有 $a_i$ 个石子，每轮可以选择一个深度至少为 $k$ 的节点并移动任意多石子到其 $k$ 级祖先处，对每个结点询问如果将其作为根谁会赢。 $n\le 10^5 , k\le 20 , a_i\le 10^9$

题目描述

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.

输入输出样例

输入样例 #1

5 1
1 2
1 3
5 2
4 3
0 3 2 4 4

输出样例 #1

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: - 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.