CF766E Mahmoud and a xor trip

Mahmoud 和 Ehab 生活在一个有 $n$ 个城市的国家，这些城市编号从 $1$ 到 $n$，由 $n-1$ 条无向道路连接。保证任意两个城市之间都可以通过这些道路到达。每个城市都有一个附加的数字 $a_{i}$。 我们定义从城市 $x$ 到城市 $y$ 的距离为，从 $x$ 到 $y$ 的路径上所有城市的数字的异或值（包括 $x$ 和 $y$ 本身）。换句话说，若路径上的城市数字形成数组 $p$，长度为 $l$，那么它们之间的距离为 $p_1 \oplus p_2 \oplus \dots \oplus p_l$，其中 $\oplus$ 表示按位异或运算。 Mahmoud 和 Ehab 想选择两个城市，从其中一个出发前往另一个。起点城市的编号一定不大于终点城市的编号（也可以选择同一个城市，此时距离等于该城市上的数字）。他们不知道如何选取两个城市，因此他们会尝试所有起点和终点组合，要求终点的编号大于等于起点。他们想知道所有这样的城市对之间的距离之和。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示城市数量。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$0 \leq a_i \leq 10^6$），其中 $a_i$ 是第 $i$ 个城市上的数字。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n, u \neq v$），表示城市 $u$ 和城市 $v$ 之间有一条无向道路。保证任意两个城市之间都连通。

输出一个整数，表示所有城市对之间的总距离。

按位异或操作会对两个等长的二进制整数的每一位对应进行逻辑异或。仅当一位上的两个数中有且只有一个为 $1$ 时，该位结果为 $1$，否则为 $0$。你可以在这里查看更多关于异或操作的介绍：[https://en.wikipedia.org/wiki/Bitwise_operation#XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 在第一个样例中，所有可选的路径有： - 从城市 $1$ 到自身，距离为 $1$； - 从城市 $2$ 到自身，距离为 $2$； - 从城市 $3$ 到自身，距离为 $3$； - 从城市 $1$ 到城市 $2$，距离为 $1 \oplus 2 = 3$； - 从城市 $1$ 到城市 $3$，距离为 $1 \oplus 2 \oplus 3 = 0$； - 从城市 $2$ 到城市 $3$，距离为 $2 \oplus 3 = 1$。 所以所有城市对之间的总距离是 $1+2+3+3+0+1=10$。 由 ChatGPT 5 翻译