CF1926G.Vlad and Trouble at MIT

Vladislav has a son who really wanted to go to MIT. The college dormitory at MIT (Moldova Institute of Technology) can be represented as a tree with $n$ vertices, each vertex being a room with exactly one student. A tree is a connected undirected graph with $n$ vertices and $n-1$ edges.

Tonight, there are three types of students:

• students who want to party and play music (marked with $\texttt{P}$),
• students who wish to sleep and enjoy silence (marked with $\texttt{S}$), and
• students who don't care (marked with $\texttt{C}$).

Initially, all the edges are thin walls which allow music to pass through, so when a partying student puts music on, it will be heard in every room. However, we can place some thick walls on any edges — thick walls don't allow music to pass through them.

The university wants to install some thick walls so that every partying student can play music, and no sleepy student can hear it.

Because the university lost a lot of money in a naming rights lawsuit, they ask you to find the minimum number of thick walls they will need to use.

弗拉迪斯拉夫有一个儿子，非常想去麻省理工学院（MIT）。麻省理工学院（摩尔多瓦理工学院）的宿舍楼可建模为一棵包含 $n$ 个顶点的树，每个顶点代表一个房间，且每个房间恰好住着一名学生。树是一种具有 $n$ 个顶点和 $n-1$ 条边的连通无向图。

今晚，学生分为以下三类：

• 想开派对并播放音乐的学生（用 $\texttt{P}$ 标记），
• 想睡觉并享受安静的学生（用 $\texttt{S}$ 标记），
• 对此无所谓的学生（用 $\texttt{C}$ 标记）。

最初，所有边都代表薄墙，允许音乐穿透；因此，一旦某位想开派对的学生开始播放音乐，整栋楼（即每个房间）都能听到。然而，我们可以在任意边上安装厚墙——厚墙会阻隔音乐传播。

校方希望安装若干厚墙，使得每位想开派对的学生均可自由播放音乐，且没有任何想睡觉的学生能听到音乐。

由于该校在一场冠名权诉讼中损失了大量资金，他们请你找出所需安装的厚墙的最少数量。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree.

The second line of each test case contains $n-1$ integers $a_2, \dots , a_n$ ($1 \leq a_i \lt i$) — it means there is an edge between $i$ and $a_i$ in the tree.

The third line of each test case contains a string $s$ of length $n$ consisting of characters $\texttt{P}$, $\texttt{S}$, and $\texttt{C}$, denoting that student $i$ is of type $s_i$.

The sum of $n$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）—— 表示树中顶点的数量。

每个测试用例的第二行包含 $n-1$ 个整数 $a_2, \dots , a_n$（$1 \leq a_i \lt i$）—— 表示树中存在一条连接顶点 $i$ 与 $a_i$ 的边。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $s$，其字符仅由 $\texttt{P}$、$\texttt{S}$ 和 $\texttt{C}$ 组成，表示学生 $i$ 的类型为 $s_i$。

所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, output a single integer — the minimum number of thick walls needed.

对于每个测试用例，输出一个整数——所需厚墙的最小数量。

In the first case, we can install one thick wall between rooms $1$ and $2$, as shown below. We cannot install $0$ walls, since then the music from room 3 will reach room 2 where a student wants to sleep, so the answer is $1$. There are other valid solutions.

在第一种情况下，我们可以在房间 $1$ 和 $2$ 之间安装一堵厚墙，如下图所示。我们不能安装 $0$ 堵墙，因为否则房间 $3$ 的音乐会传到房间 $2$，而那里有一名学生想要睡觉，因此答案为 $1$。还有其他有效的解决方案。