XOR Sum#10653
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.
The first line contains the number of vertices n~(2 \le n \le 10^5) in the graph. The next n - 1 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 ).
Print the sum of XOR sums between all pairs of vertices.
Example 1