← 返回题目列表

Codeforces · 1676/G

G. 白黑平衡子树

中文机器翻译题面 查看原题

给你一个有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。根是顶点$$$1$$$。还有一个字符串 $$$s$$$ 表示每个顶点的颜色:如果 $$$s_i = \texttt{B}$$$,则顶点 $$$i$$$ 为黑色,如果 $$$s_i = \texttt{W}$$$,则顶点 $$$i$$$ 为白色。

如果白色顶点的数量等于黑色顶点的数量,则该树的子树被称为平衡的。计算平衡子树的数量。

树是无环的连通无向图。有根树是具有选定顶点(称为根)的树。在这个问题中,所有树都有根$$$1$$$。

该树由父数组 $$$a_2, \dots, a_n$$$ 指定,其中包含 $$$n-1$$$ 数字:$$$a_i$$$ 是所有 $$$i = 2, \dots, n$$$ 的编号为 $$$i$$$ 的顶点的父节点。顶点 $$$u$$$ 的父顶点是从 $$$u$$$ 到根的简单路径上的下一个顶点。

顶点 $$$u$$$ 的子树是在到根的简单路径上经过 $$$u$$$ 的所有顶点的集合。例如,在下图中,$$$7$$$ 位于 $$$3$$$ 的子树中,因为简单路径 $$$7 \to 5 \to 3 \to 1$$$ 经过 $$$3$$$。请注意,顶点包含在其子树中,而根的子树是整棵树。

该图显示了 $$$n=7$$$、$$$a=[1,1,2,3,3,5]$$$ 和 $$$s=\texttt{WBBWWBW}$$$ 的树。顶点 $$$3$$$ 处的子树是平衡的。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 4000$$$) — 树中的顶点数。

每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$a_2, \dots, a_n$$$ ($$$1 \le a_i < i$$$) - 顶点 $$$2, \dots, n$$$ 的父节点。

每个测试用例的第三行包含一个长度为$$$n$$$的字符串$$$s$$$,由字符$$$\texttt{B}$$$和$$$\texttt{W}$$$组成——树的颜色。

保证所有测试用例的值 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——平衡子树的数量。

示例

输入 #1

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

输出 #1

2
1
4

注意

第一个测试用例如声明中所示。只有顶点 $$$2$$$ 和 $$$3$$$ 处的子树是平衡的。

在第二个测试用例中,只有顶点 $$$1$$$ 处的子树是平衡的。

在第三个测试用例中,只有顶点 $$$1$$$、$$$3$$$、$$$5$$$ 和 $$$7$$$ 处的子树是平衡的。