The Candy Cane Path

Description

Santa’s North Pole road network is a TREE with festive lights:

• There are $n$ towns, numbered from $1$ to $n$.
• There are undirected roads between some of the towns.
• The roads form a tree (connected, acyclic).
• Each road has lights that are either Red or Green.

A route between two towns $u$ and $v$ is the unique path between them in the tree. Santa calls a route a "candy cane" if the road colors strictly alternate along that path (e.g., R, G, R, G or G, R, G, R). No two consecutive roads on the route are allowed to have the same color of lights.

Santa wants to know:
How many pairs of towns are connected by a candy cane path?

You must count all unordered pairs of towns $(u, v)$ where $u \neq v$, such that the unique path between town $u$ and town $v$ is a candy cane.

Input Specification

• The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$).
• The next $n-1$ lines describe the roads. Each line contains u v c:
  • $u, v$: The towns connected by the road.
  • $c$: The color of the lights, either 'R' (Red) or 'G' (Green).

Output Specification

Output a single integer representing the number of unordered pairs $(u, v)$ such that the path between $u$ and $v$ is a candy cane.

Sample Cases

Sample Input

Sample Output