[Solution] White-Black Balanced Subtrees solution codeforces

White-Black Balanced Subtrees solution codeforces – 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} = B$ , then vertex $i$ is black, and if $s_{i} = W$ , then vertex $i$ is white.

[Solution] White-Black Balanced Subtrees solution codeforces

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.

A 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.

$\text{[math]}$ The picture shows the tree for

n = 7

a = [1, 1, 2, 3, 3, 5]

, and

s = WBBWWBW

. The subtree at the vertex

3

is balanced.

[Solution] White-Black Balanced Subtrees solution codeforces

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

The first line of each test case contains an integer $n$ ( $2 \leq n \leq 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 \leq a_{i} < 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 $B$ and $W$ — the coloring of the tree.

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.

[Solution] White-Black Balanced Subtrees solution codeforces

Example

input

Copy

3
7
1 1 2 3 3 5
WBBWWBW
2
1
BW
8
1 2 3 4 5 6 7
BWBWBWBW

output

Copy

2
1
4

[Solution] White-Black Balanced Subtrees solution codeforces

The first test case is pictured in the statement. Only the subtrees at vertices $2$ and $3$ are balanced.

In the second test case, only the subtree at vertex $1$ is balanced.

In the third test case, only the subtrees at vertices $1$ , $3$ , $5$ , and $7$ are balanced.

[Solution] White-Black Balanced Subtrees solution codeforces

[Solution] White-Black Balanced Subtrees solution codeforces

[Solution] White-Black Balanced Subtrees solution codeforces

[Solution] White-Black Balanced Subtrees solution codeforces

[Solution] White-Black Balanced Subtrees solution codeforces

For Solution

“Click here“

Leave a Comment Cancel reply