Problem Description

Given a tree with $n$ nodes, each node has a weight. The weight of a path is defined as the result of the XOR operation on the weights of all nodes along the path.

Your task is to find the sum of the weights 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$ space-separated integers $v_i$, where the $i$-th integer represents the weight of node $i$.

The next $N-1$ lines each contain two integers $a_j$ and $b_j$, indicating that there is an edge between nodes $a_j$ and $b_j$.

Output Format

Output the sum of the weights of all paths.

Sample Input and Output

Input Sample #1

3
1 2 3
1 2
2 3

Output Sample #1

10

Input Sample #2

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

Output Sample #2

64

Input Sample #3

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

Output Sample #3

85

Notes

Sample 1 Explanation

The weight of path $1 \to 1$ is $1$;

The weight of path $1 \to 2$ is $1⊕2=3$;

The weight of path $1 \to 3$ is $1⊕2⊕3=0$;

The weight of path $2 \to 2$ is $2$;

The weight of path $2 \to 3$ is $2⊕3=1$;

The weight of path $3 \to 3$ is $3$.

The sum of the weights of all paths is $1+3+0+2+1+3=10$.

Data Size and Constraints

For $30\%$ of the data, $N \le 200$.

For $50\%$ of the data, $N \le 1000$.

For another $20\%$ of the data, each node $x$ in $1,2,\cdots,N-1$ is connected to node $x+1$ by an edge.

For $100\%$ of the data, $1 \le a_j,b_j \le N \le 10^5$, $0 \le v_i \le 3 \times 10^6$.

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $90$.

The problem is translated from COCI2018-2019 CONTEST #2 T3 Deblo.

见题面 Input 部分

见题面 Output 部分