Nutella Tree (Easy)

Interview

Time limit2sMemory limit1024 MB

Summary

Count paths in a red/black tree that start at a black vertex and continue through only red vertices, with at least two vertices.

Level: Medium5 of 10
Topics: Tree, DFS, Implementation, Combinatorics
Solved: No attempts yet

Problem

Minje has a tree with $N$ vertices. Each vertex of this tree is colored either red or black.

Looking at this tree full of red and black vertices, Minje thought of Nutella. Nutella is Minje's favorite chocolate jam, and its logo looks like the following. Note that the first letter is black and the remaining letters are red.

Minje wonders how many Nutella logos can be found in the tree.

Define a sequence of distinct vertices $[v_1, v_2, \cdots\!, v_k]$ satisfying all of the following conditions as a Nutella path.

$k$ is at least $2$ .
For each $1 \le i \le k-1$ , $v_i$ and $v_{i+1}$ are directly connected by an edge in the tree.
$v_1$ is black.
For each $2 \le i \le k$ , $v_i$ is red.

Find the total number of Nutella paths in the given tree.

Input

The first line gives the number of vertices $N$ of the tree. ( $2 \le N \le 100\,000$ )

Over the following $(N-1)$ lines, the numbers $u_i$ , $v_i$ of the two vertices connected by each edge are given, separated by spaces. ( $1 \le u_i \le N$ , $1 \le v_i \le N$ , $u_i \neq v_i$ )

The next line gives a string $C$ of length $N$ consisting only of the letters B and R. The $i$ -th character of $C$ represents the color of vertex $i$ , where B means black and R means red.

Output

Print the number of Nutella paths on the first line.

Hint

The tree given as the example is drawn as follows.

Examples1

Example 1
Input
```
6
1 3
2 4
5 3
4 6
3 4
RRBRRB
```
Expected output
```
6
```