Summer Institute @ University of Central Florida: Contest 3, Problem 5

The wonderful thing about cycles is you always get back to where you started and things come full circle. The wonderful thing about trees is that when any edge is added to the graph, a cycle is formed. Edward would like to combine these wonderful things.

You are given some cities and roads between them. The layout of the city network forms a tree. That is, it is always possible to reach some city from some other through a sequence of roads, but there is always one unique simple path between any two cities. Each road has a color, either red or blue. You would like to add a single road to the network (also either red or blue) and create a balanced cycle (one where the number of red edges equals the number of blue edges). When adding a road you must ensure the road does not already exist between the two cities. Your task is to count the number of ways you select a pair of different cities and create balanced cycles. All roads are bidirectional.

Input Specification

The first line contains one integer ~n~ ~(1 \le n \le 10^5)~, the number of cities. The next ~n-1~ lines contain two integers ~a_i~ and ~b_i~ ~(1 \le a_i \ne b_i \le n)~ and a letter ~c_i \in \{r, b\}~, representing a road between cities ~a_i~ and ~b_i~ with color ~c_i~. The letter r represents a red road and the letter b represents a blue road.

Output Specification

Output the number of balanced cycles you can form.

Sample Input 1

6
1 2 r
2 3 b
2 4 r
4 6 b
4 5 b

Sample Output 1

4

Sample Input 2

7
1 2 r
2 3 b
3 4 r
4 5 b
5 6 r
6 7 b

Sample Output 2

6