310758: CF1882D. Tree XOR

D. Tree XORtime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExampleInput

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

Output

8 6 12 10 
0 

Note

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.

题目大意：给定一棵有n个顶点（从1到n标号）的树，每个顶点i上写有一个整数a_i (i=1,2,…,n)。你可以通过执行一些（可能是零个）咒语来使所有a_i相等。假设你以某个顶点为根来建立树，每次施法可以选择任意顶点v和任意非负整数c，然后对于v的子树中的所有顶点i，将a_i替换为a_i ⊕ c。这个咒语的花费是s*c，其中s是子树中的顶点数。这里⊕表示按位异或操作。设m_r为以顶点r为根使得所有a_i相等所需的最小总花费。求出m_1, m_2,…, m_n。

输入数据格式：每个测试包含多个测试案例。第一行包含测试案例数t (1≤t≤10^4)。接下来是每个测试案例的描述。每个测试案例的第一行包含一个整数n (1≤n≤2*10^5)。第二行包含n个整数a_1, a_2,…, a_n (0≤a_i<2^20)。接下来的n-1行每行包含两个整数u和v (1≤u, v≤n)，表示存在一条连接顶点u和v的边。保证给定的边构成一棵树。保证所有测试案例的n之和不超过2*10^5。

输出数据格式：对于每个测试案例，在新的一行中输出m_1, m_2,…, m_n。题目大意：给定一棵有n个顶点（从1到n标号）的树，每个顶点i上写有一个整数a_i (i=1,2,…,n)。你可以通过执行一些（可能是零个）咒语来使所有a_i相等。假设你以某个顶点为根来建立树，每次施法可以选择任意顶点v和任意非负整数c，然后对于v的子树中的所有顶点i，将a_i替换为a_i ⊕ c。这个咒语的花费是s*c，其中s是子树中的顶点数。这里⊕表示按位异或操作。设m_r为以顶点r为根使得所有a_i相等所需的最小总花费。求出m_1, m_2,…, m_n。 输入数据格式：每个测试包含多个测试案例。第一行包含测试案例数t (1≤t≤10^4)。接下来是每个测试案例的描述。每个测试案例的第一行包含一个整数n (1≤n≤2*10^5)。第二行包含n个整数a_1, a_2,…, a_n (0≤a_i<2^20)。接下来的n-1行每行包含两个整数u和v (1≤u, v≤n)，表示存在一条连接顶点u和v的边。保证给定的边构成一棵树。保证所有测试案例的n之和不超过2*10^5。 输出数据格式：对于每个测试案例，在新的一行中输出m_1, m_2,…, m_n。