Description

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.

Input Format

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 Format

Output the sum of the values of all paths.

3
1 2 3
1 2
2 3

10

5
2 3 4 2 1
1 2
1 3
3 4
3 5

64

6
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6

85

Hint

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 CONTEST #2 T3 Deblo.

Translated by ChatGPT 5