Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

XOR Tree

By shefin · 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\textbf{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)F(X) as the sum of all G(i)G(i) where XX is the special vertex of the tree. More formally,
F(X)=i=1NG(i), where X is the special vertexF(X) = \sum\limits_{i=1}^{N} G(i),\space where\space X\space is\space the\space special\space 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\textbf{XOR}, you can read this.


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

In each of the test cases, the first line will contain an integer N(1N2×105)N(1\leq N\leq2\times10^5), the number of vertices of the tree. The next line will contain NN space-separated integers A1,A2,...,AN(0Ai109)A_1, A_2 ,...,A_N(0\leq A_i\leq 10^9), where AiA_i the value written on vertex ii. Each of the next (N1)(N-1) lines will contain two integers UU and VV denoting there is an undirected edge between vertex UU and vertex VV (1U,VN;UV)(1\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}.


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


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


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



83% Solution Ratio

BigBagEarliest, 3w ago

amurtoFastest, 0.3s

serotoninLightest, 32 MB

serotoninShortest, 1333B


Login to submit


Let's say we have some numbers. In bthb^{th}bth bit of the numbers, if 111 appears ccc times, this b...

Related Contests