## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## White-Black Balanced Subtrees Codeforces Solution | Codeforces Problem Solution 2022

G. White-Black Balanced Subtrees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$. The root is vertex $1$. There is also a string $s$ denoting the color of each vertex: if ${s}_{i}=\mathtt{\text{B}}$, then vertex $i$ is black, and if ${s}_{i}=\mathtt{\text{W}}$, then vertex $i$ is white.

A subtree of the tree is called balanced if the number of white vertices equals the number of black vertices. Count the number of balanced subtrees.

tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root. In this problem, all trees have root $1$.

The tree is specified by an array of parents ${a}_{2},\dots ,{a}_{n}$ containing $n-1$ numbers: ${a}_{i}$ is the parent of the vertex with the number $i$ for all $i=2,\dots ,n$. The parent of a vertex $u$ is a vertex that is the next vertex on a simple path from $u$ to the root.

The subtree of a vertex $u$ is the set of all vertices that pass through $u$ on a simple path to the root. For example, in the picture below, $7$ is in the subtree of $3$ because the simple path $7\to 5\to 3\to 1$ passes through $3$. Note that a vertex is included in its subtree, and the subtree of the root is the entire tree. The picture shows the tree for $n=7$$a=\left[1,1,2,3,3,5\right]$, and $s=\mathtt{\text{WBBWWBW}}$. The subtree at the vertex $3$ is balanced.
Input

The first line of input contains an integer $t$ ($1\le t\le {10}^{4}$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2\le n\le 4000$) — the number of vertices in the tree.

The second line of each test case contains $n-1$ integers ${a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}) — the parents of the vertices $2,\dots ,n$.

The third line of each test case contains a string $s$ of length $n$ consisting of the characters $\mathtt{\text{B}}$ and $\mathtt{\text{W}}$ — the coloring of the tree.

Most Similar Words Codeforces Solution

It is guaranteed that the sum of the values $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, output a single integer — the number of balanced subtrees.