Tree and XOR

A tree with $n$ vertices is given. Each vertex is numbered from $1$ to $n$, and vertex $i$ has an integer $a_i$ written on it. You may perform as many operations as you want to make every $a_i$ equal.

In one operation, you choose a vertex $v$ and a non-negative integer $c$. Then, for every vertex $i$ in the subtree rooted at $v$, you replace $a_i$ with $a_i \oplus c$. Let $s$ be the size of the subtree rooted at $v$. The cost of this operation is $s \cdot c$. Here $\oplus$ denotes bitwise XOR.

Let $m_r$ be the minimum total cost needed to reach the goal when vertex $r$ is the root of the tree. Find $m_1, m_2, \ldots, m_n$.

Each input contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^{4}$). Each test case follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^{5}$).

The second line 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$ separated by a space ($1 \le u, v \le n$), denoting an edge between vertices $u$ and $v$.

The given edges are guaranteed to form a tree.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

For each test case, print $n$ integers $m_1, m_2, \ldots, m_n$ separated by spaces.

In the first test case, the goal can be reached in the following way.

1. In the first operation, choose $v=2$ and $c=1$. After the operation, $a=[3, 3, 0, 1]$. The cost of this operation is $3$.
2. In the second operation, choose $v=3$ and $c=3$. After the operation, $a=[3, 3, 3, 1]$. The cost of this operation is $3$.
3. In the third operation, choose $v=4$ and $c=2$. After the operation, $a=[3, 3, 3, 3]$. The cost of this operation is $2$.

The total cost of this process is $3+3+2=8$. It can be proven that no way reaches the goal with a cost below $8$.

$m_2$, $m_3$, and $m_4$ can be found in the same way.

In the second test case, the tree has one vertex, so the goal is already met.