CF1882D Tree XOR

给定一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。对于每个顶点 $i$（$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$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 设 $m_r$ 表示以顶点 $r$ 作为树根时，使所有 $a_i$ 相等所需的最小总代价。请你求出 $m_1, m_2, \ldots, m_n$。 $^{\dagger}$ 假设以顶点 $r$ 作为树根。如果从顶点 $i$ 到 $r$ 的简单路径上包含顶点 $v$，则顶点 $i$ 属于 $v$ 的子树。

每组测试数据包含多组测试用例。第一行包含一个整数 $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 < 2^{20}$）。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示有一条连接顶点 $u$ 和 $v$ 的边。 保证给定的边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

在第一个测试用例中，计算 $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$ 的计算方法类似。 在第二个测试用例中，目标已经达成，因为只有一个顶点。 由 ChatGPT 4.1 翻译