You are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$. The root is vertex $1$. There is also a string $s$ denoting the color of each vertex: if $s_i = {B}$, then vertex $i$ is black, and if $s_i = {W}$, then vertex $i$ is white.

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 $1$.

The tree is specified by an array of parents $a_2, \dots, a_n$ containing $n-1$ numbers: $a_i$ is the parent of the vertex with the number $i$ for all $i = 2, \dots, 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, $7$ is in the subtree of $3$ because the simple path $7 \to 5 \to 3 \to 1$ passes through $3$. 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 $n=7$, $a=[1,1,2,3,3,5]$, and $s={WBBWWBW}$. The subtree at the vertex $3$ is balanced.


-----Input-----

The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 4000$) — the number of vertices in the tree.

The second line of each test case contains $n-1$ integers $a_2, \dots, a_n$ ($1 \le a_i < i$) — the parents of the vertices $2, \dots, 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 \cdot 10^5$.


-----Output-----

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


-----Examples-----

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


-----Note-----

The first test case is pictured in the statement. Only the subtrees at vertices $2$ and $3$ are balanced.

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

In the third test case, only the subtrees at vertices $1$, $3$, $5$, and $7$ are balanced.

Difficulty: EASY
Tags: Tree algorithms

Graph algorithms

Graph traversal

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = input()
	c = 0
	d = {}
	for i in range(n):
		if g[i] == 'B':
			d[i + 1] = -1
		else:
			d[i + 1] = 1
	for i in range(n - 1):
		d[l[n - (i + 2)]] += d[n - i]
	print(list(d.values()).count(0))


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
invr = lambda : map(int, input().split())
tc = int(input())
for _ in range(tc):
	n = int(input())
	p = [int(c) - 1 for c in input().split()]
	p.insert(0, -1)
	s = input()
	arr = [0] * n
	for i in range(n - 1, -1, -1):
		if s[i] == 'W':
			arr[i] += 1
		else:
			arr[i] -= 1
		parent = p[i]
		if parent != -1:
			arr[parent] += arr[i]
	print(arr.count(0))


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		s = input()
		graph = [[] for _ in range(n)]
		for i in range(n - 1):
			graph[arr[i] - 1].append(i + 1)
		ans = [0]

		def solve(node):
			if s[node] == 'W':
				temp = -1
			else:
				temp = 1
			for nie in graph[node]:
				temp += solve(nie)
			if temp == 0:
				ans[0] += 1
			return temp
		solve(0)
		print(ans[0])
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


def solve(n, array, string):
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] += 1 if string[i] == 'B' else -1
		if i > 0:
			dp[array[i - 1] - 1] += dp[i]
	return dp.count(0)

def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		array = [int(a) for a in input().split()]
		string = input()
		print(solve(n, array, string))
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(4100)
T = int(input())
for itr in range(1, T + 1):
	n = int(input())
	parents = [0, 0] + list(map(int, input().split()))
	sons = [[] for xxx in range(n + 1)]
	for i in range(2, n + 1):
		sons[parents[i]].append(i)
	color = ['W'] + list(input().strip())
	sm = [0] * (n + 1)

	def dfs(node):
		if color[node] == 'W':
			sm[node] += 1
		else:
			sm[node] -= 1
		for subnode in sons[node]:
			dfs(subnode)
			sm[node] += sm[subnode]
	dfs(1)
	print(sm.count(0) - 1)


import sys
input = sys.stdin.readline
from collections import Counter
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	S = input().strip()
	DPB = [0] * n
	DPW = [0] * n
	ANS = 0
	for i in range(n - 1, -1, -1):
		if S[i] == 'B':
			DPB[i] += 1
		else:
			DPW[i] += 1
		if DPB[i] == DPW[i]:
			ANS += 1
		p = A[i - 1] - 1
		DPB[p] += DPB[i]
		DPW[p] += DPW[i]
	print(ANS)


for f in range(int(input())):
	n = int(input())
	p = [*map(int, input().split())]
	s = input()
	d = [0] * n
	for i in range(n - 1, -1, -1):
		d[i] += 1 if s[i] == 'W' else -1
		if i > 0:
			d[p[i - 1] - 1] += d[i]
	print(d.count(0))


I = lambda : int(input())
for _ in range(I()):
	n = I()
	p = [*map(int, input().split())]
	s = input()
	d = [0] * n
	for i in range(n - 1, -1, -1):
		d[i] += 1 if s[i] == 'W' else -1
		if i > 0:
			d[p[i - 1] - 1] += d[i]
	print(d.count(0))


t = int(input())
for _ in range(t):
	n = int(input())
	tree = [*map(int, input().split())]
	s_color = input()
	t_list = [0] * n
	for i in range(n - 1, -1, -1):
		if s_color[i] == 'W':
			t_list[i] += 1
		else:
			t_list[i] -= 1
		if i > 0:
			t_list[tree[i - 1] - 1] += t_list[i]
	print(t_list.count(0))


for _ in range(int(input())):
	n = int(input())
	l = [1] + list(map(int, input().split()))
	s = list(input())
	q = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if s[i] == 'B':
			q[i] -= 1
		else:
			q[i] += 1
		q[l[i] - 1] += q[i]
	print(q.count(0))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(4010)

def Depth_First_Search(node):
	dp[node] = 1 if color[node] == 'W' else -1
	for nextnode in cnt[node]:
		Depth_First_Search(nextnode)
		dp[node] += dp[nextnode]
for _ in range(int(input())):
	n = int(input())
	cnt = [[] for __ in range(n + 1)]
	arr = list(map(int, input().split()))
	color = [''] + list(input().strip())
	for i in range(2, n + 1):
		cnt[arr[i - 2]].append(i)
	dp = [0] * (n + 1)
	Depth_First_Search(1)
	ans = 0
	for i in range(1, n + 1):
		if dp[i] == 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [None] + [int(x) - 1 for x in input().split()]
	s = input()
	d = [0] * n
	for i in reversed(range(n)):
		d[i] += 1 if s[i] == 'B' else -1
		if i > 0:
			d[a[i]] += d[i]
	print(d.count(0))


for _ in range(int(input())):
	n = int(input())
	T = list(map(int, input().split()))
	S = input()
	d = [0] * n
	for i in range(n - 1, -1, -1):
		d[i] += 1 if S[i] == 'W' else -1
		if i != 0:
			d[T[i - 1] - 1] += d[i]
	print(d.count(0))


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	str0 = input()
	arr = [0] * n
	for i in reversed(range(n)):
		if str0[i] == 'W':
			arr[i] += 1
		else:
			arr[i] -= 1
		if i > 0:
			x = lst[i - 1] - 1
			arr[x] += arr[i]
	num = arr.count(0)
	print(num)


l = []
for tests in range(int(input())):
	(n, A, S) = (int(input()), [int(x) for x in input().split()], input().strip())
	(DPB, DPW, ANS) = ([0] * n, [0] * n, 0)
	for i in range(n - 1, -1, -1):
		if S[i] == 'B':
			DPB[i] += 1
		else:
			DPW[i] += 1
		if DPB[i] == DPW[i]:
			ANS += 1
		p = A[i - 1] - 1
		DPB[p] += DPB[i]
		DPW[p] += DPW[i]
	l.append(ANS)
[print(i) for i in l]


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = str(input())
	ct = [0] * n
	for i in reversed(range(n)):
		if s[i] == 'B':
			ct[i] = ct[i] + 1
		else:
			ct[i] = ct[i] - 1
		if i > 0:
			ct[a[i - 1] - 1] += ct[i]
	print(ct.count(0))


t = int(input())
for u in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	d = [0] * n
	for i in range(n - 1, -1, -1):
		d[i] += 1 if s[i] == 'W' else -1
		if i > 0:
			d[arr[i - 1] - 1] += d[i]
	print(d.count(0))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	g = [0] * n
	for i in reversed(range(n)):
		if s[i] == 'B':
			g[i] = g[i] - 1
		else:
			g[i] = g[i] + 1
		if i > 0:
			parent = a[i - 1] - 1
			g[parent] += g[i]
	res = g.count(0)
	print(res)


import sys
input = sys.stdin.readline
from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from functools import lru_cache
from itertools import permutations, accumulate
from bisect import insort, bisect_left, bisect_right
import threading
sys.setrecursionlimit(10 ** 4)

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	t = inp()
	for k in range(t):
		n = inp()
		arr = inlt()
		colors = insr()
		for i in range(len(colors)):
			if colors[i] == 'B':
				colors[i] = 1
			else:
				colors[i] = -1

		def solve(n, arr, colors):
			graph = defaultdict(list)
			for (i, x) in enumerate(arr):
				graph[x - 1].append(i + 1)
			count = defaultdict(int)

			def dfs(root):
				nonlocal count
				total = 0
				for node in graph[root]:
					total += dfs(node)
				total += colors[root]
				count[total] += 1
				return total
			dfs(0)
			return count[0]
		print(solve(n, arr, colors))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(node, tree, ans, s):
	ans[node] = s[node]
	for adj in tree[node]:
		ans[node] += dfs(adj, tree, ans, s)
	return ans[node]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = [[] for _ in range(n)]
	for (i, el) in enumerate(a):
		g[el - 1].append(i + 1)
	s = list((1 if char == 'B' else -1 for char in input()))
	ans = [''] * n
	dfs(0, g, ans, s)
	print(ans.count(0))


import sys
input = sys.stdin.readline
import math
sys.setrecursionlimit(10000)
import threading
threading.stack_size(2 ** 27)

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		s = input()
		g = [[] for i in range(n)]
		for i in range(n - 1):
			g[a[i] - 1].append(i + 1)
		b = [0] * n

		def Dfs(v):
			if s[v] == 'B':
				b[v] += 1
			else:
				b[v] -= 1
			for to in g[v]:
				Dfs(to)
				b[v] += b[to]
		Dfs(0)
		ans = 0
		for i in b:
			if i == 0:
				ans += 1
		print(ans)
threading.Thread(target=main).start()


import sys
sys.setrecursionlimit(5000)

def dfs(n):
	if bw_list[n] == 'W':
		(white, black) = (1, 0)
	else:
		(white, black) = (0, 1)
	result = 0
	for child in childs[n]:
		(w_child, b_child, r_child) = dfs(child)
		white += w_child
		black += b_child
		result += r_child
	if white == black:
		result += 1
	return (white, black, result)
t = int(input())
for tc in range(t):
	n = int(input())
	childs = {}
	for i in range(n + 1):
		childs[i] = []
	parants = list(map(int, input().split()))
	for i in range(len(parants)):
		childs[parants[i]].append(i + 2)
	bw_list = ' ' + input()
	result = 0
	(_, _, result) = dfs(1)
	print(result)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def solve():
	n = int(input())
	gr = [[] for _ in range(n + 1)]
	par = list(map(int, input().split()))
	for i in range(2, n + 1):
		gr[par[i - 2]].append(i)
	s = input().strip()
	wc = [0] * (n + 1)
	bc = [0] * (n + 1)
	ans = [0]

	def dfs(cur, wc, bc, gr, ans):
		wc[cur] = s[cur - 1] == 'W'
		bc[cur] = s[cur - 1] == 'B'
		for v in gr[cur]:
			dfs(v, wc, bc, gr, ans)
			wc[cur] += wc[v]
			bc[cur] += bc[v]
		ans[0] += wc[cur] == bc[cur]
	dfs(1, wc, bc, gr, ans)
	print(ans[0])
tst = int(input())
for tt in range(tst):
	solve()


from math import ceil
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def mlt():
	return map(int, input().split())
mod = int(1000000000.0 + 7)

def initmap():
	return defaultdict(lambda : 0)

class Solution:

	def __init__(self) -> None:
		x = int(input())
		s = [*mlt()]
		graph = [[] for n in range(x + 1)]
		self.st = [-1 if n == 'B' else 1 for n in input()]
		for n in range(len(s)):
			graph[s[n] - 1].append(n + 1)
		self.graph = graph
		self.res = 0
		self.dfs(0)
		print(self.res)

	def dfs(self, node):
		count = 0
		for n in self.graph[node]:
			count += self.dfs(n)
		count += self.st[node]
		if count == 0:
			self.res += 1
		return count
for _ in range(int(input())):
	Solution()


import sys
sys.setrecursionlimit(5000)

def dfs(i):
	d[i] = 1 if s[i] == 'B' else -1
	for j in g[i]:
		dfs(j)
		d[i] += d[j]
for _ in range(int(input())):
	n = int(input())
	g = [[] for _ in range(n)]
	for (i, p) in enumerate(input().split(), start=1):
		g[int(p) - 1].append(i)
	s = input()
	d = [None] * n
	dfs(0)
	print(d.count(0))


from collections import deque, defaultdict, Counter
from bisect import bisect_left as bl, bisect_right as br
import sys
import io, os
sys.setrecursionlimit(300005)
mod = 1000000007
input = sys.stdin.readline
global ans

def dfs(v, p):
	global ans
	(w, b) = (0, 0)
	if color[v - 1] == 'W':
		w += 1
	else:
		b += 1
	for nbr in child[v]:
		(w1, b1) = dfs(nbr, v)
		w += w1
		b += b1
	if w == b:
		ans += 1
	return (w, b)

def ints():
	return list(map(int, input().split()))
t = int(input())
for _ in range(t):
	n = int(input())
	child = {i: [] for i in range(1, n + 1)}
	arr = ints()
	color = input()
	for i in range(n - 1):
		child[arr[i]].append(i + 2)
	ans = 0
	dfs(1, -1)
	print(ans)


import sys
import bisect

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	p = list(map(int, inp().split()))
	s = inp()
	G = [[] for i in range(n + 1)]
	for i in range(2, n + 1):
		G[p[i - 2]].append(i)
	q = [1]
	i = 0
	while i < len(q):
		x = q[i]
		i += 1
		for v in G[x]:
			q.append(v)
	b = [0] * (n + 1)
	w = [0] * (n + 1)
	ans = 0
	for i in range(len(q) - 1, -1, -1):
		x = q[i]
		if s[x - 1] == 'B':
			b[x] = 1
		else:
			w[x] = 1
		for v in G[x]:
			b[x] += b[v]
			w[x] += w[v]
		if b[x] == w[x]:
			ans += 1
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys

def inp(*, cf=lambda x: x):
	return cf(input())

def inpint():
	return inp(cf=int)

def inp_line(*, cf=lambda x: x, s=' '):
	return list(map(cf, input().split(s)))

def inpints():
	return inp_line(cf=int)

def intstostr(l):
	return ' '.join([str(x) for x in l])

def listtostr(l):
	return ' '.join(l)
sys.setrecursionlimit(10 ** 6)

def dfs(tree, balance, v):
	for u in tree[v]:
		dfs(tree, balance, u)
		balance[v] += balance[u]

def test_case(case):
	n = inpint()
	p = inp_line(cf=lambda x: int(x) - 1)
	c = inp()
	tree = [[] for _ in range(n)]
	for i in range(len(p)):
		tree[p[i]].append(i + 1)
	balance = [1 if c[i] == 'W' else -1 for i in range(n)]
	dfs(tree, balance, 0)
	ans = 0
	for i in range(len(balance)):
		if balance[i] == 0:
			ans += 1
	return ans

def main():
	T = inpint()
	for t in range(1, T + 1):
		print(test_case(t))
main()


import sys
sys.setrecursionlimit(10 ** 6)

def main():
	t = int(input())
	while t:
		n = int(input())
		g = [[] for _ in range(n)]
		ls = list(map(int, input().split()))
		for (i, p) in enumerate(ls):
			g[i + 1].append(p - 1)
			g[p - 1].append(i + 1)
		c = input()
		size = [0] * n
		for (i, ch) in enumerate(c):
			if ch == 'W':
				size[i] = 1
			else:
				size[i] = -1

		def dfs(cur, par):
			for v in g[cur]:
				if v == par:
					continue
				dfs(v, cur)
				size[cur] += size[v]
		dfs(0, -1)
		ans = 0
		for v in size:
			if not v:
				ans += 1
		print(ans)
		t -= 1
main()


from collections import defaultdict
import sys
sys.setrecursionlimit(5000)

class Solution:

	def solve(self):
		for _ in range(int(input())):
			self.count = 0
			n = int(input())
			a = [int(x) for x in input().split()]
			self.color = input()
			self.tree = defaultdict(list)
			for i in range(n - 1):
				self.tree[a[i]].append(i + 2)
			self.dfs(1)
			print(self.count)

	def dfs(self, node):
		res = 1 if self.color[node - 1] == 'W' else -1
		for neighbor in self.tree[node]:
			res += self.dfs(neighbor)
		if res == 0:
			self.count += 1
		return res
Solution().solve()


import sys
import threading

def children_list(n, a):
	a = [elem - 1 for elem in a]
	children = []
	for i in range(n):
		children.append([])
	for i in range(n - 1):
		children[a[i]].append(i + 1)
	return children

def func(ch_list, elem, s):
	elem_children = ch_list[elem]
	w_count = 0
	b_count = 0
	ans = 0
	if len(elem_children) == 0:
		if s[elem] == 'W':
			return (1, 0, 0)
		else:
			return (0, 1, 0)
	for num in elem_children:
		colors = func(ch_list, num, s)
		w_count += colors[0]
		b_count += colors[1]
		ans += colors[2]
	if s[elem] == 'W':
		w_count += 1
	else:
		b_count += 1
	if w_count == b_count:
		ans += 1
	return (w_count, b_count, ans)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		s = input()
		elem = 0
		ch_list = children_list(n, a)
		ans = func(ch_list, elem, s)
		print(ans[2])
sys.setrecursionlimit(2 * 10 ** 5)
threading.stack_size(2 * 10 ** 6)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
import math
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 6)

def main():
	n = int(sys.stdin.readline())
	ls = list(map(int, sys.stdin.readline().split()))
	colors = sys.stdin.readline()
	g = [[] for _ in range(n)]
	for (i, v) in enumerate(ls):
		g[v - 1].append(i + 1)
		g[i + 1].append(v - 1)
	dp_w = [0] * n
	dp_b = [0] * n

	def dfs(ver, par):
		if colors[ver] == 'W':
			dp_w[ver] = 1
		else:
			dp_b[ver] = 1
		for u in g[ver]:
			if u != par:
				dfs(u, ver)
				dp_w[ver] += dp_w[u]
				dp_b[ver] += dp_b[u]
	dfs(0, -1)
	ans = 0
	for i in range(n):
		if dp_w[i] == dp_b[i]:
			ans += 1
	print(ans)
t = int(sys.stdin.readline())
while t:
	main()
	t -= 1


import collections, sys
sys.setrecursionlimit(10 ** 6)

def solve(u, d, s, ans):
	if len(d[u]) == 0:
		return 1 if s[u - 1] == 'B' else -1
	c = 0
	if s[u - 1] == 'B':
		c += 1
	else:
		c -= 1
	for v in d[u]:
		c += solve(v, d, s, ans)
	if c == 0:
		ans[0] += 1
	return c
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	d = collections.defaultdict(list)
	for i in range(n - 1):
		d[a[i]].append(i + 2)
	ans = [0]
	solve(1, d, s, ans)
	print(ans[0])


from collections import defaultdict
import sys

def solve():
	G = defaultdict(list)
	for (i, par) in enumerate(parents):
		G[par].append(i + 2)

	def dfs(node):
		(d, w, b) = (0, 0, 0)
		if col[node - 1] == 'W':
			w += 1
		else:
			b += 1
		for child in G[node]:
			(cd, cw, cb) = dfs(child)
			d += cd
			w += cw
			b += cb
		if w == b:
			d += 1
		return (d, w, b)
	(ans, _, _) = dfs(1)
	return ans
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
number_of_cases = int(input())
for case_num in range(1, number_of_cases + 1):
	N = int(input())
	parents = [int(x) for x in input().split()]
	col = input().strip()
	sys.stdout.write(f'{solve()}' + '\n')


from collections import *
import sys
sys.setrecursionlimit(1 << 30)
t = int(input())
for _ in range(t):
	n = input()
	graph = defaultdict(list)
	parents = [int(i) for i in input().split()]
	color = input().strip()
	for i in range(len(parents)):
		graph[parents[i]].append(i + 2)
	count = 0
	r = [0]

	def dfs(node, r):
		b = w = 0
		if color[node - 1] == 'W':
			w += 1
		else:
			b += 1
		for child in graph[node]:
			(b1, w1) = dfs(child, r)
			b += b1
			w += w1
		if b == w:
			r[0] += 1
		return (b, w)
	dfs(1, r)
	print(r[0])


from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	d = defaultdict(list)
	k = 1
	for i in a:
		d[i - 1].append(k)
		k += 1
	state_list = [-1] * n
	ans = 0
	for i in range(n - 1, -1, -1):
		state_list[i] = 1 if s[i] == 'W' else -1
		for j in d[i]:
			state_list[i] += state_list[j]
		if state_list[i] == 0:
			ans += 1
	print(ans)


import sys
sys.setrecursionlimit(5000)
for _ in range(int(input())):
	n = int(input())
	g = [[] for _ in range(n + 1)]
	for (i, p) in enumerate(list(map(int, input().split()))):
		g[p].append(i + 2)
	s = input()
	res = [0]

	def dfs(i=1):
		(w, b) = (int(s[i - 1] == 'W'), int(s[i - 1] == 'B'))
		if not g[i]:
			return (w, b)
		for nbr in g[i]:
			(wi, bi) = dfs(nbr)
			(w, b) = (w + wi, b + bi)
		if w == b:
			res[0] += 1
		return (w, b)
	dfs()
	print(res[0])


import sys
sys.setrecursionlimit(10 ** 6)

def solve():
	n = int(input())
	p = list(map(int, input().split()))
	for i in range(n - 1):
		p[i] -= 1
	s = input()
	graph = [[] for _ in range(n)]
	for i in range(n - 1):
		graph[p[i]].append(i + 1)
	leaf = []
	for v in range(n):
		if len(graph[v]) == 0:
			leaf.append(v)
	cnt = 0

	def dfs(v):
		nonlocal cnt
		black = 0
		white = 0
		if s[v] == 'W':
			white += 1
		else:
			black += 1
		for nv in graph[v]:
			(b, w) = dfs(nv)
			black += b
			white += w
		if black == white:
			cnt += 1
		return (black, white)
	dfs(0)
	print(cnt)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def solution2(content, color, n):
	result = [[0, 0, 0] for _ in range(n)]
	for i in range(len(content) - 1, -1, -1):
		node = i + 1
		if color[node] == 'B':
			result[node][0] += 1
		else:
			result[node][1] += 1
		if result[node][0] == result[node][1]:
			result[node][2] += 1
		parent = content[i] - 1
		result[parent][0] += result[node][0]
		result[parent][1] += result[node][1]
		result[parent][2] += result[node][2]
	node = 0
	if color[node] == 'B':
		result[node][0] += 1
	else:
		result[node][1] += 1
	if result[node][0] == result[node][1]:
		result[node][2] += 1
	print(result[0][2])
t = int(input())
for i in range(t):
	n = int(input())
	content = [int(i) for i in input().split()]
	color = list(input())
	solution2(content, color, n)


from collections import Counter
from functools import lru_cache
from bisect import bisect, bisect_left
import sys
t = int(input())
result = []
sys.setrecursionlimit(10000000)
for _ in range(t):
	n = int(input())
	parents = list(map(int, input().split()))
	string = input()
	hashMap = {i: [] for i in range(1, n + 1)}
	for i in range(len(parents)):
		(path, toPath) = (i + 2, parents[i])
		hashMap[toPath].append(path)

	def dfs(currentNode):
		neighbourNodes = hashMap[currentNode]
		(cntWhite, cntBlack) = (0, 0)
		if string[currentNode - 1] == 'W':
			cntWhite += 1
		else:
			cntBlack += 1
		ans = 0
		for neighbour in neighbourNodes:
			(answer, countWhite, countBlack) = dfs(neighbour)
			ans += answer
			cntWhite += countWhite
			cntBlack += countBlack
		if cntWhite == cntBlack:
			return (ans + 1, cntWhite, cntBlack)
		return (ans, cntWhite, cntBlack)
	(ans, _, _) = dfs(1)
	print(ans)


t = int(input())
ret = []
from sys import setrecursionlimit
setrecursionlimit(300000)
for I in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	G = [[] for _ in range(n)]
	for i in range(n - 1):
		G[a[i] - 1].append(i + 1)
		G[i + 1].append(a[i] - 1)
	memo = [-100] * n

	def dfs(before, now):
		if now != 0 and len(G[now]) == 1:
			if s[now] == 'W':
				memo[now] = 1
				return 1
			else:
				memo[now] = -1
				return -1
		else:
			if memo[now] != -100:
				return memo[now]
			cnt = 0
			for next in G[now]:
				if next == before:
					continue
				if memo[next] != -100:
					cnt += memo[next]
				else:
					cnt += dfs(now, next)
			if s[now] == 'W':
				cnt += 1
			else:
				cnt -= 1
			memo[now] = cnt
			return cnt
	dfs(-1, 0)
	ret.append(memo.count(0))
print(*ret, sep='\n')


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 5)
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline
t = int(input())

def solve():
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	s = input().strip('\n')
	d = defaultdict(list)
	for i in range(n - 1):
		d[a[i]].append(i + 2)
	ans = 0

	def go(node):
		(bc, wc) = (0, 0)
		if s[node - 1] == 'W':
			wc += 1
		else:
			bc += 1
		for child in d[node]:
			(cbc, cwc) = go(child)
			bc += cbc
			wc += cwc
		nonlocal ans
		ans += bc == wc
		return (bc, wc)
	go(1)
	print(ans)
while t:
	solve()
	t -= 1


import sys
sys.setrecursionlimit(10 ** 6)
t = int(input())

def dfs(x):
	seen[x] = 1
	for v in graph[x]:
		if seen[v] == 1:
			continue
		dp[x] += dfs(v)
	return dp[x]
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	S = input()
	seen = [0] * n
	graph = [[] for _ in range(n)]
	dp = [0] * n
	for i in range(n):
		if S[i] == 'W':
			dp[i] = 1
		else:
			dp[i] = -1
	for i in range(n - 1):
		frm = i + 1
		to = A[i] - 1
		graph[frm].append(to)
		graph[to].append(frm)
	dfs(0)
	print(dp.count(0))


from sys import setrecursionlimit
setrecursionlimit(5000)

def dfs(root, tree, coloring):
	res = 0

	def count_dfs(root):
		nonlocal res
		if root not in tree:
			white = 1 if coloring[root - 1] == 'W' else 0
			black = 1 if coloring[root - 1] != 'W' else 0
			return (white, black)
		(white, black) = (0, 0)
		for child in tree[root]:
			(w, b) = count_dfs(child)
			white += w
			black += b
		white = white + 1 if coloring[root - 1] == 'W' else white
		black = black + 1 if coloring[root - 1] != 'W' else black
		if white == black:
			res += 1
		return (white, black)
	count_dfs(root)
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	parents = list(map(int, input().split()))
	coloring = input()
	tree = {}
	for (idx, node) in enumerate(parents):
		vertex = idx + 2
		tree[node] = tree.get(node, [])
		tree[node].append(vertex)
	print(dfs(1, tree, coloring))


import sys

class TreeNode:

	def __init__(self, x):
		self.val = x
		self.children = []
sys.setrecursionlimit(10000)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	nodes = [TreeNode(x) for x in s]
	for (i, parent) in enumerate(a):
		nodes[parent - 1].children.append(nodes[i + 1])

	def dfs(node):
		if node is None:
			return (0, 0)
		balance = cnt = 0
		for child in node.children:
			(b, cntc) = dfs(child)
			balance += b
			cnt += cntc
		if node.val == 'B':
			balance += 1
		else:
			balance -= 1
		cnt += balance == 0
		return (balance, cnt)
	(_, cnt) = dfs(nodes[0])
	print(cnt)


import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

def input():
	return sys.stdin.readline().strip()

def dfs(x, p):
	for i in g[x]:
		if i != p:
			p = dfs(i, x)
			dp[x][0] += p[0]
			dp[x][1] += p[1]
	if s[x - 1] == 'B':
		dp[x][0] += 1
	else:
		dp[x][1] += 1
	return dp[x]
for test in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = input()
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = (i + 2, arr[i])
		g[a].append(b)
		g[b].append(a)
	dp = [[0, 0] for i in range(n + 1)]
	dfs(1, 0)
	ans = 0
	for i in dp:
		if i[0] == i[1]:
			ans += 1
	print(ans - 1)


from sys import setrecursionlimit
import threading
setrecursionlimit(10 ** 7)

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		c = input()
		c = 'p' + c
		a.insert(0, 0)
		visit = [0 for i in range(n + 1)]
		adj = [[] for i in range(n + 1)]

		def add_edge(u, v):
			adj[u].append(v)
			adj[v].append(u)
		stack = []
		dp = [0 for i in range(n + 1)]

		def dfs(u):
			visit[u] = 1
			if c[u] == 'W':
				dp[u] = 1
			else:
				dp[u] = -1
			for v in adj[u]:
				if visit[v] == 0:
					visit[v] = 1
					stack.append(v)
					dfs(v)
					if c[v] == 'W':
						dp[u] += dp[v]
					else:
						dp[u] += dp[v]
		for i in range(1, n):
			add_edge(a[i], i + 1)
		dfs(1)
		print(dp[1:].count(0))
threading.stack_size(10 ** 7)
t = threading.Thread(target=main)
t.start()
t.join()


from collections import defaultdict
import sys
sys.setrecursionlimit(pow(10, 9))

def dfs(src, par):
	(count, white) = (0, 0)
	for ele in graph[src]:
		if par != ele:
			(a, b) = dfs(ele, src)
			count += a
			white += b
	count += 1
	white += string[src] == 'W'
	if white == count - white:
		ans[0] += 1
	return (count, white)
t = int(input())
for _ in range(t):
	ans = [0]
	n = int(input())
	graph = defaultdict(lambda : [])
	parent = list(map(int, input().split()))
	string = input()
	for i in range(2, n + 1):
		graph[i].append(parent[i - 2])
		graph[parent[i - 2]].append(i)
	string = '0' + string
	dfs(1, -1)
	print(ans[0])


from collections import defaultdict
from sys import setrecursionlimit as srl
srl(10 ** 5)
for _ in range(int(input())):
	g = defaultdict(list)
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n - 1):
		g[i + 2].append(l[i])
		g[l[i]].append(i + 2)
	s = input()
	vis = [0] * (n + 1)
	val = [0] * (n + 1)

	def dfs(cn):
		vis[cn] = 1
		if s[cn - 1] == 'B':
			val[cn] = -1
		else:
			val[cn] = 1
		for nn in g[cn]:
			if vis[nn] == 0:
				dfs(nn)
				val[cn] += val[nn]
	dfs(1)
	res = 0
	for i in val:
		if i == 0:
			res += 1
	print(res - 1)


import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	dict1 = {}
	dict2 = {}
	for i in range(len(s)):
		dict2[i + 1] = s[i]
	for i in range(len(a)):
		if a[i] not in dict1:
			dict1[a[i]] = [i + 2]
		else:
			dict1[a[i]] += [i + 2]
	for i in range(1, n + 1):
		if i not in dict1:
			dict1[i] = []
	dp = {}
	for i in range(n, 0, -1):
		if dict1[i] == []:
			if dict2[i] == 'W':
				dp[i] = (1, 0)
			else:
				dp[i] = (0, 1)
		else:
			cntw = 0
			cntb = 0
			if dict2[i] == 'W':
				cntw += 1
			else:
				cntb += 1
			for j in dict1[i]:
				cntw += dp[j][0]
				cntb += dp[j][1]
			dp[i] = (cntw, cntb)
	cnt = 0
	for i in dp:
		if dp[i][0] == dp[i][1]:
			cnt += 1
	print(cnt)


t = int(input())
ans = []
import sys
sys.setrecursionlimit(500000)
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	tek = 0
	s1 = []
	for i in s:
		s1.append(i)
	dp = [[0, 0] for i in range(n)]
	use = [0] * n

	def dfs(v):
		use[v] = 1
		if s1[v] == 'W':
			dp[v][0] += 1
		else:
			dp[v][1] += 1
		for i in rb[v]:
			if use[i] == 0:
				dfs(i)
				dp[v][0] += dp[i][0]
				dp[v][1] += dp[i][1]
	rb = [[] for i in range(n)]
	for i in range(len(a)):
		rb[a[i] - 1].append(i + 1)
	dfs(0)
	for i in dp:
		if i[0] == i[1]:
			tek += 1
	ans.append(tek)
for i in ans:
	print(i)


from sys import stdin, stdout, setrecursionlimit
import collections
import math

def solve(graph, n):
	if n in graph and graph[n] != []:
		g = [0, 0]
		color = s[n - 1]
		for ne in graph[n]:
			k = solve(graph, ne)
			g[0] += k[0]
			g[1] += k[1]
		if color == 'B':
			g[0] += 1
		else:
			g[1] += 1
		check[n] = g
	else:
		color = s[n - 1]
		g = [0, 0]
		if color == 'B':
			g[0] += 1
		else:
			g[1] += 1
		check[n] = g
	return check[n]

def main():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		global graph
		graph = {}
		global s
		s = input().strip()
		for i in range(1, n + 1):
			graph[i] = []
		for i in range(n - 1):
			graph[l[i]].append(i + 2)
		global check
		check = {}
		solve(graph, 1)
		ans = 0
		for i in check:
			x = check[i]
			if x[0] == x[1]:
				ans += 1
		print(ans)
	return
setrecursionlimit(10 ** 9)
input = stdin.readline
main()


import sys
sys.setrecursionlimit(2 * 10 ** 5 + 1)
vc = []
sum = []

def dfs(u, v):
	for z in vc[u]:
		if z == v:
			continue
		else:
			dfs(z, u)
			sum[u] += sum[z]
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	vc = []
	sum = []
	s = input()
	for i in range(0, n + 2):
		sum.append(0)
		vc.append([])
	for i in range(0, n):
		if s[i] == 'B':
			sum[i + 1] = 1
		else:
			sum[i + 1] = -1
	for i in range(1, n):
		vc[a[i - 1]].append(i + 1)
		vc[i + 1].append(a[i - 1])
	dfs(1, 0)
	ans = 0
	for i in range(1, n + 1):
		if sum[i] == 0:
			ans += 1
	print(ans)


from collections import *

def get_int():
	return int(input())

def get_nums():
	return list(map(int, input().split()))

def main():
	test = get_int()
	for _ in range(test):
		n = get_int()
		nums = get_nums()
		color = input()
		graph = defaultdict(list)
		for (index, value) in enumerate(nums):
			graph[value].append(index + 2)
		dp = [[0, 0] for _ in range(n + 1)]
		ans = [0]

		def dfs(root, parent):
			dp[root][0] = color[root - 1] == 'W'
			dp[root][1] = color[root - 1] == 'B'
			for child in graph[root]:
				if child != parent:
					dfs(child, root)
					dp[root][0] += dp[child][0]
					dp[root][1] += dp[child][1]
			ans[0] += dp[root][0] == dp[root][1] > 0
		dfs(1, -1)
		print(ans[0])
import threading
import sys
sys.setrecursionlimit(1 << 27)
main_threading = threading.Thread(target=main)
main_threading.start()
main_threading.join()


import sys
sys.setrecursionlimit(10 ** 5)
import bisect
t = int(input())

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	s = input()
	cnt = [0] * (n + 1)
	E = {i: set() for i in range(1, n + 1)}
	for i in range(n - 1):
		E[A[i]].add(i + 2)

	def dfs(x):
		if s[x - 1] == 'W':
			(w, b) = (1, 0)
		else:
			(w, b) = (0, 1)
		for y in E[x]:
			(tw, tb) = dfs(y)
			w += tw
			b += tb
		cnt[x] = [w, b]
		return (w, b)
	dfs(1)
	ans = 0
	for i in range(1, n + 1):
		if cnt[i][0] == cnt[i][1]:
			ans += 1
	print(ans)
for _ in range(t):
	solve()


import sys
sys.setrecursionlimit(10 ** 6)

class TreeNode:

	def __init__(self, val, col):
		self.val = val
		self.col = col
		self.ch = []

	def inord(self):
		print(self.val)
		for c in self.ch:
			c.inord()

def balcnt(root):
	if root == None:
		return [0, 0]
	allw = 0
	allb = 0
	for c in root.ch:
		(w, b) = balcnt(c)
		allw += w
		allb += b
	if root.col == 0:
		allw += 1
	else:
		allb += 1
	if allw == allb:
		cnt[0] += 1
	return [allw, allb]
t = int(input())
for tc in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	s = input()
	root = TreeNode(1, 0 if s[0] == 'W' else 1)
	nodes = [root]
	for i in range(1, n):
		nodes.append(TreeNode(i + 1, 0 if s[i] == 'W' else 1))
	for i in range(n - 1):
		par = nodes[p[i] - 1]
		cur = nodes[i + 2 - 1]
		par.ch.append(cur)
	cnt = [0]
	balcnt(root)
	print(cnt[0])


import sys, threading
sys.setrecursionlimit(10 ** 4)

def dfs(x):
	global v, adj, l, c, ans
	v[x] = 1
	if c[x - 1] == 'W':
		l[x][0] = 1
	else:
		l[x][1] = 1
	for i in adj[x]:
		if not v[i]:
			dfs(i)
			l[x][0] += l[i][0]
			l[x][1] += l[i][1]
	if l[x][0] == l[x][1]:
		ans += 1

def main():
	global v, adj, l, c, ans
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		c = list(input())
		v = [0] * (n + 1)
		adj = [[] for i in range(n + 1)]
		l = [[0, 0] for i in range(n + 1)]
		ans = 0
		for i in range(n - 1):
			adj[i + 2].append(a[i])
			adj[a[i]].append(i + 2)
		dfs(1)
		print(ans)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	s = input()
	adj_list = {}
	for i in range(n):
		adj_list[i] = []
	for i in range(n - 1):
		cur = a[i]
		adj_list[cur - 1].append(i + 1)
	cts = [[0, 0] for i in range(n)]

	def fun(root):
		childs = adj_list[root]
		(w, b) = (0, 0)
		if s[root] == 'W':
			w += 1
		else:
			b += 1
		for chi in childs:
			if sum(cts[chi]) == 0:
				(w1, b1) = fun(chi)
			else:
				(w1, b1) = (cts[chi][0], cts[chi][1])
			w += w1
			b += b1
		(cts[root][0], cts[root][1]) = (w, b)
		return (w, b)
	fun(0)
	ans = 0
	for i in range(n):
		if cts[i][0] == cts[i][1]:
			ans += 1
	print(ans)


import sys
sys.setrecursionlimit(10000000)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	graph = {x: [] for x in range(1, n + 1)}
	color = input()
	for (i, item) in enumerate(a):
		graph[item].append(i + 2)
	white_memo = {x: 0 for x in range(1, n + 1)}

	def f_white(x):
		if white_memo.get(x):
			return white_memo[x]
		if color[x - 1] == 'W':
			ans = 1
		else:
			ans = 0
		for item in graph[x]:
			ans += f_white(item)
		white_memo[x] = ans
		return ans
	black_memo = {x: 0 for x in range(1, n + 1)}

	def f_black(x):
		if black_memo.get(x):
			return black_memo[x]
		if color[x - 1] == 'B':
			ans = 1
		else:
			ans = 0
		for item in graph[x]:
			ans += f_black(item)
		black_memo[x] = ans
		return ans
	f_white(1)
	f_black(1)
	same = 0
	for (key, value) in white_memo.items():
		if black_memo[key] == value:
			same += 1
	print(same)


def task(n, a, s):
	leafs = dict()
	for i in range(1, n + 1):
		leafs[i] = True
	leafs[1] = False
	for i in a:
		leafs[i] = False
	parents = dict()
	parents[1] = None
	for i in range(2, n + 1):
		parents[i] = a[i - 2]
	childs = dict()
	for i in range(n - 1):
		if not a[i] in childs:
			childs[a[i]] = set()
		childs[a[i]].add(i + 2)
	cache = dict()
	queue = []
	for key in leafs.keys():
		if leafs[key]:
			queue.append(key)
		if s[key - 1] == 'W':
			cache[key] = 1
		else:
			cache[key] = -1
	total = 0
	while len(queue):
		item = queue.pop()
		if cache[item] == 0:
			total += 1
		parent = parents[item]
		if item != 1:
			childs[parent].remove(item)
			cache[parent] += cache[item]
			if len(childs[parent]) == 0:
				queue.insert(0, parent)
	print(total)
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	task(n, a, s)