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.
The first line contains the number of vertices n (2≤n≤105) 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).
Print the sum of XOR sums between all pairs of vertices.