← 返回题目列表

Codeforces · 1882/D

D. 树异或

中文机器翻译题面 查看原题

给您一棵树,其中 $$$n$$$ 顶点标记为从 $$$1$$$ 到 $$$n$$$。整数 $$$a_{i}$$$ 被写在顶点 $$$i$$$ 上,$$$i = 1, 2, \ldots, n$$$。您希望通过执行一些(可能是零)咒语来使所有 $$$a_{i}$$$ 相等。

假设您将树的根设在某个顶点。在每个法术上,您可以选择任何顶点 $$$v$$$ 和任何非负整数 $$$c$$$。然后对于$$$v$$$的子树$$$^{\dagger}$$$中的所有顶点$$$i$$$,将$$$a_{i}$$$替换为$$$a_{i}\oplus c$$$。此法术的成本为 $$$s \cdot c$$$,其中 $$$s$$$ 是子树中的顶点数。这里$$$\oplus$$$表示按位异或运算。

如果选择顶点 $$$r$$$ 作为树的根,则令 $$$m_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$$$。

示例

输入 #1

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

输出 #1

8 6 12 10 
0

注意

在第一个测试用例中,为了找到 $$$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$$$。

在第二个测试用例中,目标已经实现,因为只有一个顶点。