Christmas Game (Codeforces 1498F)
Tags: Math, games

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.

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.

Note: Let us calculate the answer for sample input with root node as 1 and as 2.Root node 1Alice 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 2Bob 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.

Sample Inputs:
5 1
1 2
1 3
5 2
4 3
0 3 2 4 4

Sample Outputs:
1 0 0 1 1

Solution (Python):
import sys
from sys import stdin
from collections import deque
(n, k) = map(int, stdin.readline().split())
(N, K) = (n, k)
lis = [[] for i in range(N)]
for i in range(N - 1):
    (x, y) = map(int, stdin.readline().split())
    x -= 1
    y -= 1
    lis[x].append(y)
    lis[y].append(x)
a = list(map(int, stdin.readline().split()))
p = [i for i in range(N)]
vlis = []
q = deque([0])
while q:
    v = q.popleft()
    vlis.append(v)
    for nex in lis[v]:
        if nex != p[v]:
            p[nex] = v
            q.append(nex)
dp = [[0] * (2 * k) for i in range(N)]
for ind in range(N - 1, -1, -1):
    v = vlis[ind]
    dp[v][0] ^= a[v]
    for nex in lis[v]:
        if nex != p[v]:
            for nk in range(2 * k):
                dp[v][(nk + 1) % (2 * k)] ^= dp[nex][nk]
ans = [None] * N
for v in vlis:
    if v == 0:
        now = 0
        for i in range(k, 2 * k):
            now ^= dp[v][i]
        ans[v] = min(now, 1)
    else:
        pcopy = [dp[p[v]][i] for i in range(2 * k)]
        for i in range(2 * k):
            pcopy[(i + 1) % (2 * k)] ^= dp[v][i]
        for i in range(2 * k):
            dp[v][(i + 1) % (2 * k)] ^= pcopy[i]
        now = 0
        for i in range(k, 2 * k):
            now ^= dp[v][i]
        ans[v] = min(now, 1)
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
E = [[] for i in range(n)]
for i in range(n - 1):
    (a, b) = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
A = list(map(int, input().split()))
N = n + 1
ROOT = 0
QUE = [ROOT]
Parent = [-1] * (N + 1)
Parent[ROOT] = N
TOP_SORT = []
while QUE:
    x = QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to] == -1:
            Parent[to] = x
            QUE.append(to)
UP = [[0] * (2 * k) for i in range(n)]
DOWN = [[0] * (2 * k) for i in range(n)]
for x in TOP_SORT[::-1]:
    UP[x][0] ^= A[x]
    if Parent[x] != N:
        for i in range(2 * k):
            UP[Parent[x]][(i + 1) % (2 * k)] ^= UP[x][i]
SUM = [[0] * (2 * k) for i in range(n)]
for i in range(1, n):
    for j in range(2 * k):
        SUM[Parent[i]][j] ^= UP[i][j]
for i in TOP_SORT[1:]:
    p = Parent[i]
    XX = [0] * (2 * k)
    for j in range(2 * k):
        XX[j] = SUM[p][j] ^ UP[i][j]
    DOWN[i][0] ^= A[p]
    for j in range(2 * k):
        DOWN[i][j] ^= XX[(j - 1) % (2 * k)]
    for j in range(2 * k):
        SUM[i][j] ^= DOWN[i][j]
ANS = [0] * n
for i in range(n):
    if i == ROOT:
        continue
    p = Parent[i]
    for j in range(k - 1, 2 * k - 1):
        ANS[p] ^= UP[i][j]
        ANS[i] ^= DOWN[i][j]
for i in range(n):
    if ANS[i] != 0:
        ANS[i] = 1
print(*ANS)

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

def rerooting():
    dp = [[E] * len(edge[v]) for v in range(n)]
    memo = [E] * n
    for v in order[::-1]:
        res = E
        for i in range(len(edge[v])):
            if edge[v][i] == par[v]:
                continue
            dp[v][i] = memo[edge[v][i]]
            res = merge(res, f(dp[v][i], edge[v][i]))
        memo[v] = g(res, v)
    memo2 = [E] * n
    for v in order:
        for i in range(len(edge[v])):
            if edge[v][i] == par[v]:
                dp[v][i] = memo2[v]
        s = len(edge[v])
        cumR = [E] * (s + 1)
        cumR[s] = E
        for i in range(s, 0, -1):
            cumR[i - 1] = merge(cumR[i], f(dp[v][i - 1], v))
        cumL = E
        for i in range(s):
            if edge[v][i] != par[v]:
                val = val = merge(cumL, cumR[i + 1])
                memo2[edge[v][i]] = g(val, v)
            cumL = merge(cumL, f(dp[v][i], edge[v][i]))
    ans = [E for i in range(n)]
    for v in range(n):
        res = E
        for i in range(len(edge[v])):
            res = merge(res, f(dp[v][i], edge[v][i]))
        ans[v] = g(res, v)
    return ans

def f(res, v):
    return res

def g(res, v):
    nxt = [res[(i - 1) % (2 * k)] for i in range(2 * k)]
    nxt[0] ^= A[v]
    return nxt

def merge(a, b):
    c = [i ^ j for (i, j) in zip(a, b)]
    return c
''
from sys import stdin
input = lambda : stdin.readline()[:-1]
(n, k) = map(int, input().split())
E = [0] * 2 * k
edge = [[] for i in range(n)]
for i in range(n - 1):
    (x, y) = map(lambda x: int(x) - 1, input().split())
    edge[x].append(y)
    edge[y].append(x)
A = list(map(int, input().split()))
from collections import deque
order = []
par = [-1] * n
todo = deque([0])
while todo:
    v = todo.popleft()
    order.append(v)
    for u in edge[v]:
        if u != par[v]:
            par[u] = v
            todo.append(u)
ans = rerooting()
ANS = [0] * n
for i in range(n):
    g = 0
    for j in range(k):
        g ^= ans[i][k + j]
    if g:
        ANS[i] = 1
print(*ANS)