题目描述

在一个魔法学院中，有一个奇特的魔法森林，这片森林由 $n$ 棵魔法树组成，由 $n-1$ 条魔法链接使其两两可互达，也就是说将魔法树视为节点，魔法链接视为边，这个魔法森林构成一棵树。

每棵魔法树上刻有一个魔法数字 $a_i$。你的任务是通过施展一些魔法咒语，使得所有魔法树上的魔法数字相同。

你可以将魔法森林的某棵树设为魔法源（即树的根节点）。每次施展咒语时，你可以选择一个节点 $v$ 和一个非负整数 $c$，然后对从该节点为根的子树（包括该节点本身）上的所有节点同时施加魔法操作，将它们的魔法数字 $a_i$ 替换为 $a_i \oplus c$，其中 $\oplus$ 表示按位异或操作。这次咒语的施法代价为 $s \cdot c$，其中 $s$ 是这棵子树的节点个数。

对于这个魔法森林，如果选择不同的魔法树作为魔法源，施展魔法的最小总代价可能会有所不同。定义 $m_r$ 为将所有魔法数字变为相等的最小总代价，其中第 $r$ 棵魔法树被选为魔法源。你的任务是计算出 $m_1, m_2, \ldots, m_n$ 的值。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_{1\sim n}$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示第 $u,v$ 棵魔法树之间有魔法链接。

输出格式

对于每组数据，输出一行 $n$ 个整数 $m_1,m_2,\cdots,m_n$。

2
4
3 2 1 0
1 2
2 3
2 4
1
100

8 6 12 10 
0

样例解释 1

• 在第一个测试用例中，当将魔法树 1 作为魔法源时，计算最小代价的过程如下：
  1. 第一次咒语选择节点 2 和 c = 1 ，咒语施加后，魔法数字变为 [3, 3, 0, 1] ，代价为 3 。
  2. 第二次咒语选择节点 3 和 c = 3 ，咒语施加后，魔法数字变为 [3, 3, 3, 1] ，代价为 3 。
  3. 第三次咒语选择节点 4 和 c = 2 ，咒语施加后，魔法数字变为 [3, 3, 3, 3] ，代价为 2 。

总代价为 3 + 3 + 2 = 8 。

对于其他魔法树作为魔法源的情况，可以通过类似的方法计算。

• 在第二个测试用例中，由于只有一棵魔法树，魔法数字已经相等，因此代价为 0 。

数据范围

对于 $30\%$ 的数据，$1\leq n,\sum n\leq 10$，$0\leq a_i<2$。

对于 $60\%$ 的数据，$1\leq n,\sum n\leq 5000$，$0\leq a_i<2^{10}$。

对于 $100\%$ 的数据，$1\leq T\leq 10^4$，$1\leq n,\sum n\leq 2\times 10^5$，$0\leq a_i<2^{20}$。