Summer Institute '17 Contest 3 P5 - Balanced Cycles

View as PDF

Submit solution

Points: 20
Time limit: 3.0s
Memory limit: 256M

Problem types
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

The first line contains one integer n (1 \le n \le 10^5), the number of cities. The next n-1 lines contains two integers a_i and b_i (1 \le a_i  \neq 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

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

Comments

There are no comments at the moment.