Making UCPC

Time limit3sMemory limit1024 MB

Summary

Given a tree whose vertices are labeled U, C, or P, count pairs (a, b) whose path letters can be rearranged into (UCPC)^k for some k >= 1.

Level: Hard8 of 10
Topics: Tree, DFS, Combinatorics, Math
Solved: No attempts yet

Problem

A tree with $N$ vertices is given. Each vertex of the tree is numbered from 1 to $N$ and has one of the letters U, C, P written on it. Count the number of ordered pairs $(a, b)$ satisfying the condition below. $(1 \leq a < b \leq N)$

After collecting the letters written on all vertices on the simple path from vertex $a$ to vertex $b$ , they can be rearranged to form a string of the form $($ UCPC $)^k$ . ( $k \geq 1$ )

Input

The first line gives the number of vertices $N$ . $(1 \leq N \leq 200\ 000)$

The next line gives a string $S$ of length $N$ consisting only of the letters U, C, P.

The next $N-1$ lines give two integers $u_i$ and $v_i$ separated by a space. This means that vertices $u_i$ and $v_i$ are directly connected in the tree. $(1 \leq u_i, v_i \leq N, u_i \neq v_i)$

Output

Print the number of ordered pairs $(a, b)$ satisfying the condition.

Hint

The tree for sample 1 is shown below.

Figure J.1: the tree for sample 1

Using the path between vertex 1 and vertex 4, or between vertex 1 and vertex 5, a string of the form $k=1$ (UCPC) can be made.

In sample 2, two strings of the form $k=1$ (UCPC) and one string of the form $k=2$ (UCPCUCPC) can be made.

Examples2

Example 1
Input
```
5
UCCPP
2 3
4 3
3 5
2 1
```
Expected output
```
2
```

Example 2

Input

13
CUUUCCCCPCCPP
1 2
2 3
4 7
3 10
6 2
7 6
12 13
9 7
7 8
11 12
7 11
5 7

Expected output