Tree XOR
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$$$.
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.
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}$$$.
For each test case, print $$$m_1, m_2, \ldots, m_n$$$ on a new line.
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())
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)
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)