CF1882D.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$ .

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.

In the first test case, to find $m_1$ we root the tree at vertex $1$ .

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$ .
2. 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$ .
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.