XOR Sum
Very easy
Execution time limit is 1 second
Runtime memory usage limit is 128 megabytes
The tree with vertices is given. The edges of the tree have weights of only or . Let’s find the XOR sum between all pairs of vertices. Compute the sum of all XOR sums.
Input
The first line contains the number of vertices in the graph. The next lines describe the edges. Each line contains three integers: the numbers of the vertices connected by the edge (vertices are numbered from to ) and the weight of the edge ( or ).
Output
Print the sum of XOR sums between all pairs of vertices.
Examples
Input #1
Answer #1
Submissions 449
Acceptance rate 50%