Vlad and Trouble at MIT
Contest: Codeforces Round 928 (Div. 4)
Difficulty rating: 1900
Tags: dfs and similar, dp, flows, graphs, greedy, implementation, trees

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.

Input format:
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 < 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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS

Example output:
1
1
2

Editorial:
Let's think of the problem as trying to separate some rooms(with P and possibly some C) that will hear music and the other ones(with S and possibly some C) that will not hear music. Imagine red "water" from the P nodes and blue "water" flowing from the S nodes flowing freely until hitting a thick wall. We don't want these two "waters" to mix.
Let's rotate the tree upside down so that on top are all the leaves and end with the root node at the bottom and start letting blue and red water flow down. We want to check so that, at any point, these waters don't mix. Let's go through them layer by layer and do dynamic programming $$$dp_{i, 3}$$$ where for each node $$$i$$$, we remember the minimum number of walls we have to add such that only red water flows there, only blue water flows, or no water flows, ensuring there is no mixing in nodes above. Using the $$$dp$$$ values for the nodes above, we can calculate the $$$dp$$$ value of the node below. Of course, the $$$dp$$$ value for the "pumping" nodes (P or S) will have the $$$dp$$$ of other colors infinite.
The final answer will be the minimum of $$$dp_{1, 0}$$$, $$$dp_{1, 1}$$$, $$$dp_{1, 2}$$$, the minimum number of walls needed for the root to not reach "water"(and no mixing above), to reach only red "water"(and no mixing above) or reach only blue "water"(and no mixing above).
Final complexity is $$$\mathcal{O}(n)$$$