Strange Memory

Problem Source

CCPC Changchun 2020 F

Problem Description

Once there was a rooted tree. The tree contained $n$ nodes, which were numbered $1, 2, \dots, n$. The node numbered $1$ was the root of the tree. Besides, every node $i$ was assigned a number $a_i$. You were surprised to find that there were several pairs of nodes $(i, j)$ satisfying

$$a_i \oplus a_j = a_{\mathrm{lca}(i, j)},$$

where $\oplus$ denotes the bitwise XOR operation, and $\mathrm{lca}(i, j)$ is the lowest common ancestor of $i$ and $j$, or formally, the lowest (i.e. deepest) node that has both $i$ and $j$ as descendants.

Unfortunately, you cannot remember all such pairs, and only remember the sum of $i \oplus j$ for all different pairs of nodes $(i, j)$ satisfying the above property. Note that $(i, j)$ and $(j, i)$ are considered the same here. In other words, you will only be able to recall

$$\sum_{i=1}^n \sum_{j=i+1}^n \left[ a_i \oplus a_j = a_{\mathrm{lca}(i, j)} \right](i \oplus j).$$

You are asked to calculate it now in order to memorize it better in the future.

Input Format

The first line contains a single integer $n$ ($2 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$).

Each of the next $n - 1$ lines contains $2$ integers $u$ and $v$ ($1 \le u, v \le n,\ u \neq v$), indicating that there is an edge between $u$ and $v$. It is guaranteed that these edges form a tree.

Output Format

Print what you will memorize in the future.

Sample Input

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

Sample Output

18