题目内容

小蓝正在研究一家公司的组织架构，该公司由 $n$ 个员工组成，员工之间存在 $n-1$ 条直属汇报关系，构成一棵树形结构。每个员工都有一个类别：研究员（标记为 R）或工程师（标记为 B）。

对于一个由部分员工组成的团队（即树的一个连通子图），若其中研究员的人数严格多于工程师的人数，则称之为“明星团队”。已知整家公司恰好是一个明星团队。

小蓝希望将公司拆分成两个独立的明星团队：他计划切断恰好一条直属汇报关系（即树中的一条边），使得拆分出的两个部分各自形成的团队都是明星团队。请你帮他计算有多少种切断方案。

数据范围：员工数量 $n$ 满足 $1 \le n \le 10^5$。

输入描述

第一行包含一个正整数 $n$，表示员工数量。 第二行包含一个长度为 $n$ 的、仅由字符 R 和 B 组成的字符串，第 $i$ 个字符表示第 $i$ 个员工的类别（R 表示研究员，B 表示工程师）。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示 $u$ 号员工与 $v$ 号员工之间存在一条直属汇报关系。

输出描述

输出一个整数，表示满足条件的方案数。

样例1

输入

2
RR
1 2

输出

1

说明

只有一条边 $(1,2)$。切断后两个部分各含 1 名员工，均为研究员（研究员 1 人，工程师 0 人），均满足研究员严格多于工程师，因此方案数为 $1$。

样例2

输入

3
RRB
1 2
2 3

输出

0

说明

树为链 $1-2-3$。若切断边 $(1,2)$，左侧团队为节点 1（研究员 1，工程师 0）满足条件；右侧团队为节点 2,3（研究员 1，工程师 1）研究员数不大于工程师数，不满足条件。若切断边 $(2,3)$，右侧团队为节点 3（研究员 0，工程师 1）不满足条件。故方案数为 $0$。

样例3

输入

6
RBRRRB
1 2
1 3
2 4
2 5
3 6

输出

3

说明

枚举每条边：边 $(1,2)$，子树 $\{2,4,5\}$ 研究员 2 人工程师 1 人，研究员多于工程师，剩余部分 $\{1,3,6\}$ 研究员 2 人工程师 1 人，满足条件；边 $(2,4)$，子树 $\{4\}$ 研究员 1 人工程师 0 人，剩余部分研究员 3 人工程师 2 人，满足；边 $(2,5)$ 同理满足；边 $(1,3)$，子树 $\{3,6\}$ 研究员 1 人工程师 1 人，不满足；边 $(3,6)$，子树 $\{6\}$ 研究员 0 人工程师 1 人，不满足。共 $3$ 条边满足要求，答案为 $3$。