# [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.

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Ā 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Ā 7ā5ā3ā17ā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Ā 2ā1052ā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Ā 11,Ā 33,Ā 55, andĀ 77Ā are balanced.