Migrated from Lutece 2565 Qyery on a tree

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一棵 $n$ 个节点的树，节点编号从 $1$ 到 $n$，指定 $1$ 号节点为根节点，每个节点有权值 $a_i$，计算下面这个式子的值：

$$\sum_{i=1}^n \sum_{j=i+1}^n [a_i \oplus a_j =a_{\text{LCA}(i,j)}](i \oplus j) $$

其中，$\text{LCA}(i,j)$ 表示树上 $i$ 与 $j$ 的最近公共祖先。

Input

第一行给出节点个数 $n$。 第二行给出 $n$ 个整数，从 $a_1$ 到 $a_n$。 接下来的 $n-1$ 行，每行给出两个数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 间连有一条边。

Output

输出一个正整数表示答案。

Samples

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

18

Constraints

$2 \leqslant n \leqslant 10^5$ $1 \leqslant a_i \leqslant 10^6$ $1 \leqslant u,v \leqslant n$ 且 $u \neq n$

Note

LCA：指两个节点的最近公共祖先。 这个定义只有在指定了根节点的情况下才有效。 表达式 $[x]$ 在 $x$ 为真的情况下值为 $1$，否则值为 $0$。

Resources

2021 UESTC ICPC Training for Data Structures