Calculate Visited Countries

The countries on a tree are either open (O) or restricted (R). Each operation can only turn two different R countries into O, and it can be performed zero or more times. For each starting country, choose a conversion plan separately to maximize the number of countries reachable from that start while passing only through O countries, then add up these maxima. The plans for different starts are independent; a start that cannot be opened counts as 0.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n, the second line contains an O/R string of length n, followed by n−1 lines of undirected tree edges u v (0-based). 1≤n≤50005.

输出格式

Output one integer answer.

样例 1

输入：

7
ROROROO
0 1
0 2
2 3
2 4
4 5
4 6

输出：

33

样例 2

输入：

1
R

输出：

0

样例 3

输入：

2
OR
0 1

输出：

1

样例说明

Example 1: the best reachable counts for the seven starts are 4, 4, 5, 5, 5, 5, 5, summing to 33. Example 2: the only R cannot be opened as part of a pair, so the output is 0. Example 3: the O start can only visit itself, and the R start cannot be opened, so the sum is 1.