← 返回题目列表

AtCoder · past22_j

J. 异或的异或

中文机器翻译题面 查看原题

问题陈述

有一个 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101=110).
一般来说,总异或 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