Strange Memory

题目来源

CCPC Changchun 2020 F

题目描述

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$. Your 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 assumed to calculate it now in order to memorize it better in the future.

输入格式

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

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

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

输出格式

Print what you will memorize in the future.

样例输入

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

样例输出

18