Codeforces Round 899 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

dfs and similar

dp

greedy

trees

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Tree XOR

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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.

Example

Input

243 2 1 01 22 32 41100

Output

8 6 12 10 0

Note

In the first test case, to find $$$m_1$$$ we root the tree at vertex $$$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$$$.
- 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$$$.
- 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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 08:39:03 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|