A tree with n vertices is given. The edges of the tree have a weight of 0 or 1 only. 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 graph. It is followed by n - 1 lines containing the description of edges. Every line of description consists of three integer numbers: vertices connected by the edge (labelled from 1 to n) and edge's weight (0 or 1).
Print the sum of XOR sums between the pairs of vertices.
5 1 2 1 2 3 1 2 4 0 4 5 1