问题陈述
有一个 N- 顶点树 T。 边缘 i (1\le i\le N - 1) 连接顶点 u_i 和 v_i 并且有一个重量 w_i.
对于整数对 (i,j) 与 1\le i < j\le N,让 f(i,j) 是来自顶点的简单路径中包含的边的权重的总异或 i 到顶点 j 树 T.
求总异或 f(i,j) 所有整数对 (i,j) 与 1\le i < j\le N.
什么是异或?
异或 A \oplus B 非负整数 A 和 B 定义如下。- 的 2^k的地方 (k \geq 0) 的 A \oplus B 的二进制表示是 1 如果恰好是以下之一 2^k的地方 A 和 B 在其二进制表示中是 1,和 0 否则。
一般来说,总异或 k 整数 p_1, \dots,和 p_k 定义为 (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k),可以证明与顺序无关 p_1, \dots, p_k.
约束
- 2\le N\le 2\times 10^5
- 1\le u_i < v_i\le N
- 0\le w_i< 2^{30}
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}
输出
打印答案。
示例输入 1
3 2 3 4 1 2 3
示例输出 1
0
例如,从顶点开始的简单路径中包含的边的权重 1 到顶点 3 是 3 和 4,所以 f(1,3) 是 XOR 3 和 4,即 7.
我们还可以找到 f(1,2)=3 和 f(2,3)=4,所以答案是总异或 7,3,和 4,即 0.
示例输入 2
4 1 4 8 1 2 2 1 3 5
示例输出 2
15
示例输入 3
6 3 5 3 4 5 11 1 6 7 2 3 1 1 3 4
示例输出 3
13