Tokens On A Tree Solution Codechef -You are given a rooted tree with NN nodes numbered 1,2,…,N1,2,…,N. Node 11 is the root node. Some of the nodes have a token in them. In one move,

 

Tokens On A Tree Solution Codechef -  

SOLUTION

” CLICK HERE “

You are given a rooted tree with N nodes numbered 1,2,…,N. Node 1 is the root node. Some of the nodes have a token in them. In one move, you can choose a non-root node that has a token, but its parent doesn't, and move the token from this node to its parent. What is the maximum number of moves you can make?

Note: When a token is moved out of a node, the node becomes empty, and other tokens will be able to move there.

Input

  • The first line contains an integer T, the number of test cases. Each test case contains three lines.
  • The first line of each test case contains an integer N, the number of nodes in the tree.
  • The second line contains a string s of length N. The character si is 1 if node has a token, and 0 otherwise.
  • The third line contains N−1 space separated integers, p2,p3,…pN, where pi is the parent of node i.

Output

For each test case, print the maximum number of moves that can be made on a new line.

Constraints

  • 1≤N≤106
  • For each valid i, 1≤pi<i.
  • The sum of N over all test cases doesn't exceed 106.

Subtasks

  • Subtask 1 (13 points): T≤10,N≤17.
  • Subtask 2 (18 points): The sum of N over all test cases doesn't exceed 2000.
  • Subtask 3 (41 points): The sum of N over all test cases doesn't exceed 105.
  • Subtask 4 (28 points): No additional constraints.

Sample Input

2
5
01010
1 1 3 3
5
10101
1 1 3 3

Sample Output

2
0

Explanation

In the first test case, you can first move a token from node 4 to node 3, and then move a token from node 2 to node 1.

In the second test case, there are no possible valid moves.

Reactions