Problems
XOR Sum
XOR Sum
The tree with n vertices is given. The edges of the tree have weights of only 0 or 1. Let’s find the XOR sum between all pairs of vertices. Compute the sum of all XOR sums.
Input data
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 1 to n) and the weight of the edge (0 or 1).
Output data
Print the sum of XOR sums between all pairs of vertices.
Examples
Input example #1
5 1 2 1 2 3 1 2 4 0 4 5 1
Output example #1
6