XOR Tree

shefin Criterion 2021 Round 11
Limits 2s, 512 MB

You are given a tree with NN vertices. A tree is a connected undirected graph without cycles.

The tree has exactly one special vertex XX. Each vertex ii has an integer number AiA_i written on it. Let's denote a function G(U)G(U) as the XOR of all values AiA_i written on the vertices on the simple path connecting vertex UU and the special vertex XX. Let's denote another function $F(X)$ as the sum of all $G(i)$ where $X$ is the special vertex of the tree. More formally,

F(X)=i=1NG(i)F(X) = \sum\limits_{i=1}^{N} G(i), where XX is the special vertex.

For each vertex jj, you have to print the value of F(j)F(j) treating vertex jj as the special vertex of the tree.

The simple path is the path that visits each vertex at most once. To know about XOR, you can read this.

Input

The first line of the input will contain an integer TT (1T4×1041\leq T\leq4\times10^4), the number of the test cases.

In each of the test cases, the first line will contain an integer NN (1N2×1051\leq N\leq2\times10^5), the number of vertices of the tree. The next line will contain NN space-separated integers A1A_1, A2A_2,..., ANA_N (0Ai1090\leq A_i\leq 10^9), where AiA_i the value written on vertex ii. Each of the next N1N-1 lines will contain two integers UU and VV denoting there is an undirected edge between vertex UU and vertex VV (1U,VN;UV1\leq U,V\leq N; U\neq V). It is guaranteed that the given edges form a tree.

The sum of NN over all the test cases will not be greater than 2×1052\times10^{5}.

Output

For each test case, print NN space-separated integers F(1)F(1), F(2)F(2), …, F(N)F(N) in a line, where F(j)F(j) is the function described in the statement.

Sample

InputOutput
2
3
10 23 17
1 2
2 3
4
13 56 9 35
2 4
2 3
1 2
51 58 35
148 185 136 102

Notes:

For test case 11, the tree will be like this:

The value of each vertex is written in blue. Let's see what happens when vertex 33 is the special vertex in this tree.

G(1)=102317=12G(1) = 10\oplus23\oplus 17 = 12
G(2)=2317=6G(2) = 23\oplus 17 = 6
G(3)=17G(3) = 17

So, F(3)=G(1)+G(2)+G(3)=12+6+17=35F(3) = G(1) + G(2) + G(3) = 12+6+17 = 35


Submit

Login to submit.

Contributors

Statistics

86% Solution Ratio
BigBagEarliest, Mar '21
Liad_HossainFastest, 0.2s
serotoninLightest, 32 MB
serotoninShortest, 1333B
Toph uses cookies. By continuing you agree to our Cookie Policy.