[Solution] Christmas Game Codeforces Round #711

Christmas Game Solution Codeforces

Alice and Bob are going to celebrate Christmas by playing a game with a tree of presents. The tree has nn nodes (numbered 11 to nn, with some node rr as its root). There are aiai presents are hanging from the ii-th node.

Before beginning the game, a special integer kk 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, ii) which has depth at least kk. Then, the player picks some positive number of presents hanging from that node, let’s call it mm (1≤m≤ai)(1≤m≤ai);
• the player then places these mm presents on the kk-th ancestor (let’s call it jj) of the ii-th node (the kk-th ancestor of vertex ii is a vertex jj such that ii is a descendant of jj, and the difference between the depth of jj and the depth of ii is exactly kk). Now, the number of presents of the ii-th node (ai)(ai) is decreased by mm, and, correspondingly, ajaj is increased by mm;
• 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 ii in a tree with root rr is defined as the number of edges on the simple path from node rr to node ii. The depth of root rr itself is zero.Input

The first line contains two space-separated integers nn and kk (3≤n≤105,1≤k≤20)(3≤n≤105,1≤k≤20).

The next n−1n−1 lines each contain two integers xx and yy (1≤x,y≤n,x≠y)(1≤x,y≤n,x≠y), denoting an undirected edge between the two nodes xx and yy. These edges form a tree of nn nodes.

The next line contains nn space-separated integers denoting the array aa (0≤ai≤109)(0≤ai≤109).Output

Output nn integers, where the ii-th integer is 11 if Alice wins the game when the tree is rooted at node ii, or 00 otherwise.Example

input Christmas Game Solution Codeforces

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

output Christmas Game Solution Codeforces

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.

Solution: Coming Soon

Also Read

• [Solution] GCD Sum Codeforces Round #711
• [Solution] Bananas in a Microwave Codeforces Round #711
• [Solution] Two Houses Codeforces Round #711
• [Solution] Planar Reflection Codeforces Round #711
• [Solution] Box Fitting Codeforces Round #711

Christmas Game Solution Codeforces