407578: GYM102832 F Strange Memory

Once there was a rooted tree. The tree contained $$$n$$$ nodes, which were numbered $$$1, \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_{\operatorname{lca}(i, j)},$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation, and $$$\operatorname{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\limits_{i=1}^n\sum\limits_{j=i+1}^n [a_i \oplus a_j = a_{\operatorname{lca}(i, j)}] (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, \ldots, 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