/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点の重み付き木があります。i 本目の辺は頂点 u_i と頂点 v_i を双方向に結んでいて、その重みは w_i です。
頂点の組 (x,y) について、\text{dist}(x,y) を以下のように定めます。
- x から y への最短パスに含まれる辺全ての重みの XOR
1 \leq i \lt j \leq N を満たす全ての組 (i,j) について \text{dist}(i,j) を求め、その総和を (10^9+7) で割った余りを出力してください。
\text{ XOR } とは
整数 a, b のビットごとの排他的論理和 a \text{ XOR } b は、以下のように定義されます。
- a \text{ XOR } b を二進表記した際の 2^k (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i \lt v_i \leq N
- 0 \leq w_i \lt 2^{60}
- 与えられるグラフは木
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}
出力
\text{dist}(i,j) の総和を (10^9+7) で割った余りを出力せよ。
入力例 1
3 1 2 1 1 3 3
出力例 1
6
\text{dist}(1,2)=1, \text{dist}(1,3)=3, \text{dist}(2,3)=2 であり、これらの総和は 6 です。
入力例 2
5 3 5 2 2 3 2 1 5 1 4 5 13
出力例 2
62
入力例 3
10 5 7 459221860242673109 6 8 248001948488076933 3 5 371922579800289138 2 5 773108338386747788 6 10 181747352791505823 1 3 803225386673329326 7 8 139939802736535485 9 10 657980865814127926 2 4 146378247587539124
出力例 3
241240228
(10^9+7) で割った余りを出力してください。
Score : 500 points
Problem Statement
We have a weighted tree with N vertices. The i-th edge connects Vertex u_i and Vertex v_i bidirectionally and has a weight w_i.
For a pair of vertices (x,y), let us define \text{dist}(x,y) as follows:
- the XOR of the weights of the edges in the shortest path from x to y.
Find \text{dist}(i,j) for every pair (i,j) such that 1 \leq i \lt j \leq N, and print the sum of those values modulo (10^9+7).
What is \text{ XOR }?
The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq u_i \lt v_i \leq N
- 0 \leq w_i \lt 2^{60}
- The given graph is a tree.
- All values in input are integers.
Input
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 sum of \text{dist}(i,j), modulo (10^9+7).
Sample Input 1
3 1 2 1 1 3 3
Sample Output 1
6
We have \text{dist}(1,2)=1, \text{dist}(1,3)=3, and \text{dist}(2,3)=2, for the sum of 6.
Sample Input 2
5 3 5 2 2 3 2 1 5 1 4 5 13
Sample Output 2
62
Sample Input 3
10 5 7 459221860242673109 6 8 248001948488076933 3 5 371922579800289138 2 5 773108338386747788 6 10 181747352791505823 1 3 803225386673329326 7 8 139939802736535485 9 10 657980865814127926 2 4 146378247587539124
Sample Output 3
241240228
Print the sum modulo (10^9+7).