Mahmoud 和 Ehab 生活在一个拥有 n 个城市的国家,城市编号为 1 到 n,并由 n - 1 条无向道路连接。保证您可以使用这些道路从任何其他城市到达任何城市。每个城市都有一个编号ai。
我们将从城市 x 到城市 y 的距离定义为从 x 到 y 的路径上附加到城市的数字的异或(包括 x 和 y)。换句话说,如果从 x 到 y 的路径上附加到城市的值形成长度为 l 的数组 p,则它们之间的距离为 $$p_{1} \oplus p_{2} \oplus \ldots \oplus p_{n}$$,其中 $$\bigcirc$$ 是按位异或运算。
Mahmoud 和 Ehab 想要选择两个城市并从一个城市前往另一个城市。起始城市的索引始终小于或等于结束城市的索引(它们可能在同一城市开始和结束,在这种情况下,距离等于该城市所附的数字)。他们无法确定这两个城市,因此他们尝试将每个城市作为起点,并尝试将每个指数较大的城市作为终点。他们想知道所有城市对之间的总距离。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — Mahmoud 和 Ehab 所在国家的城市数量。
然后第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 106),它们表示附加到城市的数字。整数ai 附加到城市i。
接下来的 n - 1 行每行包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v),表示城市 u 和 v 之间有一条无向道路。保证您可以使用这些道路从任何其他城市到达任何城市。
输出
输出一个数字,表示所有城市对之间的总距离。
示例
输入 #1
3 1 2 3 1 2 2 3
输出 #1
10
输入 #2
5 1 2 3 4 5 1 2 2 3 3 4 3 5
输出 #2
52
输入 #3
5 10 9 8 7 6 1 2 2 3 3 4 3 5
输出 #3
131
注意
按位异或采用两个长度相等的位整数,并对每对对应位执行逻辑异或运算。如果只有第一位为 1 或只有第二位为 1,则每个位置的结果为 1,但如果两者均为 0 或均为 1,则结果为 0。您可以在此处阅读有关按位异或运算的更多信息: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$$。