#G. ABC201E - Xor Distances

Type: Default

3000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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 $dist (x, y)$ as follows:

the XOR of the weights of the edges in the shortest path from $x$ to $y$ .

Find $dist (i, j)$ for every pair $(i, j)$ such that $1 \leq i < j \leq N$ , and print the sum of those values modulo $(1 0^{9} + 7)$ .

What is $XOR$ ?

The bitwise $X O R$ of integers $A$ and $B$ , $A X O R B$ , is defined as follows:

When $A X O R 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.

For example, we have $3 X O R 5 = 6$ (in base two: $011 X O R 101 = 110$ ).

Constraints

$2 \leq N \leq 2 \times 1 0^{5}$
$1 \leq u_{i} < v_{i} \leq N$
$0 \leq w_{i} < 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}$ 
 $⋮$ 
 $u_{N - 1}$   $v_{N - 1}$   $w_{N - 1}$

Output

Print the sum of $dist (i, j)$ , modulo $(1 0^{9} + 7)$ .

Sample Input 1

3
1 2 1
1 3 3

Sample Output 1

We have $dist (1, 2) = 1,$ $dist (1, 3) = 3,$ and $dist (2, 3) = 2$ , for the sum of $6$ .

Sample Input 2

Sample Output 2

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 $(1 0^{9} + 7)$ .

摸底测试

Not Attended

Status: Done
Rule: IOI
Problem: 8
Start at: 2023-8-3 8:30
End at: 2023-8-3 11:30
Duration: 3 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 15

#G. ABC201E - Xor Distances

ABC201E - Xor Distances

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

摸底测试

Status

Development

Support

#G. ABC201E - Xor Distances

ABC201E - Xor Distances

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

摸底测试

Status

Development

Support

Don't have an account?

SIGN IN