P7310 [COCI 2018/2019 #2] Deblo

Given a tree with $n$ nodes, where each node has a weight. The value of a path is defined as the XOR of the weights of all nodes on that path. Your task is to compute the sum of the values of all paths.

The first line contains a positive integer $N$, representing the number of nodes in the tree. The second line contains $N$ integers $v_i$ separated by spaces, where the $i$-th integer represents the weight of node $i$. The next $N - 1$ lines each contain two integers $a_j, b_j$, indicating that there is an edge between $a_j$ and $b_j$.

Output the sum of the values of all paths.

#### Explanation for Sample 1 The value of path $1 \to 1$ is $1$. The value of path $1 \to 2$ is $1⊕2=3$. The value of path $1 \to 3$ is $1⊕2⊕3=0$. The value of path $2 \to 2$ is $2$. The value of path $2 \to 3$ is $2⊕3=1$. The value of path $3 \to 3$ is $3$. The sum of the values of all paths is $1+3+0+2+1+3=10$. #### Constraints For $30\%$ of the testdata, $N \le 200$. For $50\%$ of the testdata, $N \le 1000$. For the other $20\%$ of the testdata, for every node $x = 1, 2, \cdots, N - 1$, there is an edge between node $x$ and node $x + 1$. For $100\%$ of the testdata, $1 \le a_j, b_j \le N \le 10^5$, and $0 \le v_i \le 3 \times 10^6$. #### Notes **This problem uses the original COCI scoring. The full score is $90$.** **Translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf) _T3 Deblo_.** Translated by ChatGPT 5