经典dfs

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

题目内容

网络安全团队正在审查一个树形拓扑的局域网。该网络包含 $n$ 台设备，编号从 $1$ 到 $n$，并以 $1$ 号设备为根形成一棵有根树。每台设备都有一个安全状态：安全（用 S 表示）或已被入侵（用 I 表示）。

若以某台设备为根的子树（包含该设备及其所有后代）中所有设备均为安全状态，则称该子树为“完全安全子网”。请你编写程序，统计整个网络中完全安全子网的数量。

约束：设备总数 $n$ 不超过 10^5，边的两个端点 $x, y$ 均满足 $1 \le x, y \le n$。

输入描述

第一行包含一个整数 $n$，表示设备数量。 第二行包含一个长度为 $n$ 的字符串，仅由字符 S 和 I 组成，第 $i$ 个字符为 S 表示设备 $i$ 安全，为 I 表示设备 $i$ 已被入侵。 接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示设备 $x$ 与设备 $y$ 之间有一条网线直接相连。

输出描述

输出一个整数，表示完全安全子网的数量。

样例1

输入

1
R

输出

1

说明

只有 1 个节点，且该节点为红色（R）。以该节点为根的子树就是它本身，所有节点均为红色，满足条件的子树共有 1 个。

样例2

输入

3
RWR
1 2
1 3

输出

1

说明

节点染色：节点 1 为 R，节点 2 为 W，节点 3 为 R。树结构：1-2，1-3，根为 1。 依次检查所有子树：

• 以 1 为根的子树包含 1(R)、2(W)、3(R)，不全为红色；
• 以 2 为根的子树仅含 2(W)；
• 以 3 为根的子树仅含 3(R)，全为红色。 因此只有 1 个子树所有节点均为红色。

样例3

输入

5
WRRRW
1 2
2 3
2 4
1 5

输出

3

说明

节点染色：节点 1 为 W，节点 2、3、4 为 R，节点 5 为 W。树结构：1-2，2-3，2-4，1-5，根为 1。 红色节点为 2、3、4。检查所有子树：

• 以 3 为根的子树：{3}，全为红色；
• 以 4 为根的子树：{4}，全为红色；
• 以 2 为根的子树：{2,3,4}，全为红色；
• 以 5 为根的子树：{5}，为 W；
• 以 1 为根的子树：{1,2,3,4,5}，包含 W。 满足所有节点均为红色的子树共有 3 个。