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

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

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

## [Solution] White-Black Balanced Subtrees solution codeforces

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

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.