CF1498F Christmas Game

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.

N/A

N/A

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.