/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N 頂点の木 T があります。辺 i (1\le i\le N - 1) は頂点 u_i と頂点 v_i を結んでおり、重みは w_i です。
1\le i < j\le N を満たす整数の組 (i,j) に対し、 f(i,j) を木 T の頂点 i から頂点 j への単純パスに含まれる辺の重みの総 XOR と定義します。
1\le i < j\le N を満たす整数の組 (i,j) 全てに対する f(i,j) の総 XOR を求めてください。
XOR とは
非負整数 A,B の XOR A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k \, (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, \dots, p_k の総 XOR は (\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) は 3 と 4 の XOR である 7 となります。
他にも f(1,2)=3, f(2,3)=4 が分かるので、答えは 7,3,4 の総 XORである 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
Problem Statement
There is an N-vertex tree T. Edge i (1\le i\le N - 1) connects vertices u_i and v_i and has a weight w_i.
For an integer pair (i,j) with 1\le i < j\le N, let f(i,j) be the total XOR of the weights of the edges contained in the simple path from vertex i to vertex j of the tree T.
Find the total XOR of f(i,j) over all integer pairs (i,j) with 1\le i < j\le N.
What is XOR?
The XOR A \oplus B of non-negative integers A and B is defined as follows.- The 2^ks place (k \geq 0) of A \oplus B in its binary representation is 1 if exactly one of 2^ks places of A and B in their binary representations is 1, and 0 otherwise.
In general, the total XOR of k integers p_1, \dots, and p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k), which can be proven independent of the order of p_1, \dots, p_k.
Constraints
- 2\le N\le 2\times 10^5
- 1\le u_i < v_i\le N
- 0\le w_i< 2^{30}
- The given graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}
Output
Print the answer.
Sample Input 1
3 2 3 4 1 2 3
Sample Output 1
0
For example, the weights of the edges contained in the simple path from vertex 1 to vertex 3 are 3 and 4, so f(1,3) is the XOR of 3 and 4, which is 7.
We can also find f(1,2)=3 and f(2,3)=4, so the answer is the total XOR of 7,3, and 4, which is 0.
Sample Input 2
4 1 4 8 1 2 2 1 3 5
Sample Output 2
15
Sample Input 3
6 3 5 3 4 5 11 1 6 7 2 3 1 1 3 4
Sample Output 3
13