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

给你一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。对每个 $i = 1, 2, \ldots, n$，顶点 $i$ 上写有一个整数 $a_{i}$。你可以执行若干次（可能为零次）法术，使得所有 $a_{i}$ 的值相等。

假设你将树以某个顶点为根进行定根。每次法术中，你可以任选一个顶点 $v$ 和一个非负整数 $c$；然后对 $v$ 的子树$^{\dagger}$ 中的所有顶点 $i$，将 $a_{i}$ 替换为 $a_{i} \oplus c$。该次法术的代价为 $s \cdot c$，其中 $s$ 是该子树中顶点的个数。此处 $\oplus$ 表示按位异或运算。

令 $m_r$ 表示当以顶点 $r$ 为树根时，使所有 $a_i$ 相等所需的最小总代价。请计算 $m_{1}, m_{2}, \ldots, m_{n}$。

$^{\dagger}$ 假设选定顶点 $r$ 作为树根，则顶点 $i$ 属于顶点 $v$ 的子树，当且仅当从 $i$ 到 $r$ 的简单路径经过 $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 \lt 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}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^{4}$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^{5}$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \lt 2^{20}$）。

接下来的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示顶点 $u$ 和 $v$ 之间存在一条边。

保证所给的边构成一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^{5}$。

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

对于每个测试用例，在新的一行上输出 $m_1, m_2, \ldots, m_n$。

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.

在第一个测试用例中，为求出 $m_1$，我们将树以顶点 $1$ 为根。

1. 在第一次施法中，选择 $v=2$ 和 $c=1$。施法后，数组 $a$ 变为 $[3, 3, 0, 1]$。此次施法的代价为 $3$。
2. 在第二次施法中，选择 $v=3$ 和 $c=3$。施法后，数组 $a$ 变为 $[3, 3, 3, 1]$。此次施法的代价为 $3$。
3. 在第三次施法中，选择 $v=4$ 和 $c=2$。施法后，数组 $a$ 变为 $[3, 3, 3, 3]$。此次施法的代价为 $2$。

此时，数组 $a$ 中所有值均已相等，总代价为 $3 + 3 + 2 = 8$。

类似地可求出 $m_2$、$m_3$、$m_4$。

在第二个测试用例中，目标已自然达成，因为图中仅有一个顶点。