题目描述

给定一棵有 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$，每个顶点上写有字母 U、C、P 中的一个。

请计算满足下列条件的数对 $(a,b)$ 的数量，其中 $1\le a<b\le N$：

• 收集从顶点 $a$ 到顶点 $b$ 的简单路径上所有顶点所写的字母；
• 将这些字母任意重新排列后，可以得到字符串 $(\texttt{UCPC})^k$，其中 $k\ge 1$。

换言之，路径上的字母数量必须满足：U 和 P 各有 $k$ 个，C 有 $2k$ 个。

输入格式

第一行包含一个整数 $N$。$(1\le N\le 200000)$

第二行包含一个长度为 $N$、仅由字符 U、C、P 组成的字符串 $S$。其中 $S_i$ 表示顶点 $i$ 上的字母。

接下来 $N-1$ 行，每行包含两个整数 $u_i,v_i$，表示树中顶点 $u_i$ 与 $v_i$ 之间有一条边。$(1\le u_i,v_i\le N,\ u_i\ne v_i)$

输出格式

输出满足条件的数对 $(a,b)$ 的数量。

样例

输入样例 1

5
UCCPP
2 3
4 3
3 5
2 1

输出样例 1

2

输入样例 2

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

输出样例 2

3

样例说明

图 J.1：样例 1 对应的树。路径 $1\to4$ 与 $1\to5$ 上的字母都可以重排为 UCPC。

在样例 2 中，可以构成两个 $k=1$ 的 UCPC，以及一个 $k=2$ 的 UCPCUCPC。