题目描述

给你一个有根树，由 $n$ 个从 $1$ 到 $n$ 编号的节点组成。根是节点 $1$ 。还有一个字符串 $s$ 表示每个节点的颜色：如果 $s_i=B$ ，则节点 $i$ 为黑色；如果 $s_i=W$ ，则节点 $i$ 为白色。

如果一个子树的白色节点的数量等于黑色节点的数量，则该子树为平衡子树。计算平衡子树的数量。

树是一个没有环路的连通无向图。在这个问题中，所有树的根编号为 $1$ 。

树由一个数组 $a_2,…,a_n$ 表示： $a_i$ 是第 $i$ 个节点的父节点。节点 $u$ 的父节点是指从 $u$ 到根的简单路径上的下一个节点。

节点 $u$ 的子树是在根的简单路径上通过 $u$ 的所有节点的集合。例如，在下图中， $7$ 位于 $3$ 的子树中，因为简单路径 $7→5→3→1$ 通过 $3$ 。请注意，节点包含在其子树中，根的子树是整个树。

上图展示了 $n=7，a=[1,1,2,3,3,5]，s=WBBWWBW$ 的树。顶点 $2$ 和 $3$ 处的子树是平衡的。

输入格式

第一行输入包含整数 $t(1≤t≤10^4))$ 表示测试用例数。

每个测试用例的第一行包含一个整数 $n(2≤n≤4000)$ 表示树中的节点数。

每个测试用例的第二行包含 $n−1$ 个整数 $a_2,…,a_n(1≤a_i＜i)$ 表示节点 $2,…,n$ 的父节点。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $s$ ，由字符 B 和 W 代表树的颜色。

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

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

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

2
1
4

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

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

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