[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 11 to 𝑛n. The root is vertex 11. There is also a string 𝑠s denoting the color of each vertex: if 𝑠𝑖=𝙱si=B, then vertex 𝑖i is black, and if 𝑠𝑖=𝚆si=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.

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

The tree is specified by an array of parents 𝑎2,,𝑎𝑛a2,…,an containing 𝑛1n−1 numbers: 𝑎𝑖ai is the parent of the vertex with the number 𝑖i for all 𝑖=2,,𝑛i=2,…,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, 77 is in the subtree of 33 because the simple path 75317→5→3→1 passes through 33. 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 𝑛=7n=7𝑎=[1,1,2,3,3,5]a=[1,1,2,3,3,5], and 𝑠=𝚆𝙱𝙱𝚆𝚆𝙱𝚆s=WBBWWBW. The subtree at the vertex 33 is balanced.

[Solution] White-Black Balanced Subtrees solution codeforces

The first line of input contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains an integer 𝑛n (2𝑛40002≤n≤4000) — the number of vertices in the tree.

The second line of each test case contains 𝑛1n−1 integers 𝑎2,,𝑎𝑛a2,…,an (1𝑎𝑖<𝑖1≤ai<i) — the parents of the vertices 2,,𝑛2,…,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 21052⋅105.

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 22 and 33 are balanced.

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

In the third test case, only the subtrees at vertices 113355, and 77 are balanced.

For Solution

Click here

Leave a Comment