Tree XOR (Codeforces 1882D)
Tags: Greedy, trees

You are given a tree with $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$. An integer $$$a_{i}$$$ is written on vertex $$$i$$$ for $$$i = 1, 2, \ldots, n$$$. You want to make all $$$a_{i}$$$ equal by performing some (possibly, zero) spells.Suppose you root the tree at some vertex. On each spell, you can select any vertex $$$v$$$ and any non-negative integer $$$c$$$. Then for all vertices $$$i$$$ in the subtree$$$^{\dagger}$$$ of $$$v$$$, replace $$$a_{i}$$$ with $$$a_{i} \oplus c$$$. The cost of this spell is $$$s \cdot c$$$, where $$$s$$$ is the number of vertices in the subtree. Here $$$\oplus$$$ denotes the bitwise XOR operation.Let $$$m_r$$$ be the minimum possible total cost required to make all $$$a_i$$$ equal, if vertex $$$r$$$ is chosen as the root of the tree. Find $$$m_{1}, m_{2}, \ldots, m_{n}$$$.$$$^{\dagger}$$$ Suppose vertex $$$r$$$ is chosen as the root of the tree. Then vertex $$$i$$$ belongs to the subtree of $$$v$$$ if the simple path from $$$i$$$ to $$$r$$$ contains $$$v$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$).Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting that there is an edge connecting two vertices $$$u$$$ and $$$v$$$.It is guaranteed that the given edges form a tree.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output: For each test case, print $$$m_1, m_2, \ldots, m_n$$$ on a new line.

Note: In the first test case, to find $$$m_1$$$ we root the tree at vertex $$$1$$$.   In the first spell, choose $$$v=2$$$ and $$$c=1$$$. After performing the spell, $$$a$$$ will become $$$[3, 3, 0, 1]$$$. The cost of this spell is $$$3$$$.  In the second spell, choose $$$v=3$$$ and $$$c=3$$$. After performing the spell, $$$a$$$ will become $$$[3, 3, 3, 1]$$$. The cost of this spell is $$$3$$$.  In the third spell, choose $$$v=4$$$ and $$$c=2$$$. After performing the spell, $$$a$$$ will become $$$[3, 3, 3, 3]$$$. The cost of this spell is $$$2$$$. Now all the values in array $$$a$$$ are equal, and the total cost is $$$3 + 3 + 2 = 8$$$.The values $$$m_2$$$, $$$m_3$$$, $$$m_4$$$ can be found analogously.In the second test case, the goal is already achieved because there is only one vertex.

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

Sample Outputs:
8 6 12 10 
0

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, arr) = (readInt(), readList())
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readInts()
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
    (S, par) = (n, [-1] * n)
    (st, par[0]) = ([(0, 0)], -2)
    size = [1] * n
    ans = [0] * n
    while st:
        (node, marked) = st.pop()
        if marked:
            if node == 0:
                continue
            size[par[node]] += size[node]
            ans[0] += (arr[node] ^ arr[par[node]]) * size[node]
        else:
            st.append((node, 1))
            for nei in graph[node]:
                if par[nei] == -1:
                    par[nei] = node
                    st.append((nei, 0))
    st = [0]
    while st:
        node = st.pop()
        for nei in graph[node]:
            if par[nei] == node:
                ans[nei] = ans[node] + (arr[node] ^ arr[nei]) * (S - 2 * size[nei])
                st.append(nei)
    return ans
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import queue
from sys import stdin

def input():
    return stdin.readline().rstrip()
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        (x, y) = map(int, input().split())
        x -= 1
        y -= 1
        g[x].append(y)
        g[y].append(x)
    ans = [0] * n
    cnt = [1] * n
    parent = [-1] * n
    s = []
    q = []
    q.append((0, -1))
    while q:
        (node, pr) = q.pop()
        for vecin in g[node]:
            if vecin == pr:
                continue
            parent[vecin] = node
            s.append(vecin)
            q.append((vecin, node))
    for x in s[::-1]:
        ans[0] += (a[x] ^ a[parent[x]]) * cnt[x]
        cnt[parent[x]] += cnt[x]
    for x in s:
        ans[x] = ans[parent[x]] + (a[x] ^ a[parent[x]]) * (n - cnt[x] * 2)
    print(*ans)

Solution (Python):
import queue
from sys import stdin

def input():
    return stdin.readline().rstrip()
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        (x, y) = map(int, input().split())
        x -= 1
        y -= 1
        g[x].append(y)
        g[y].append(x)
    ans = [0] * n
    cnt = [1] * n
    parent = [-1] * n
    s = []
    q = []
    q.append((0, -1))
    while q:
        (node, pr) = q.pop()
        for vecin in g[node]:
            if vecin == pr:
                continue
            parent[vecin] = node
            s.append(vecin)
            q.append((vecin, node))
    for x in s[::-1]:
        ans[0] += (a[x] ^ a[parent[x]]) * cnt[x]
        cnt[parent[x]] += cnt[x]
    for x in s:
        ans[x] = ans[parent[x]] + (a[x] ^ a[parent[x]]) * (n - cnt[x] * 2)
    print(*ans)