Queries On A Tree

You are given a tree of size N.

The edges are given by the vector P of size N-1 where ith element represents an edge between i+1 and P[i]. (1-based indexing)

You need to answer Q queries on it.

In each query, you are given a set of nodes S.

You need to find the size of the minimal connected subgraph (which will also be a tree) containg all nodes in the set S.

• 1 ≤ N, Q, summation |S| ≤ 10⁵
• 1 ≤ S[i] ≤ N

Input consists of 2 arguments, first is the array A = P of size N-1 and second is the 2D array B of size (sum |S|) x 2 representing the queries in the same order.

Here, A and B are the names of the arguments in the function provided to you.

The queries are given in the format (qid, node) where qid is the query number and node is one of the nodes in the set S[qid].

It is guaranteed that queries are numbered consecutively starting from 1.

Refer samples for more details.

Return a vector of integers, the answer to all the queries in increasing order of qid.

Input 1:

 P = [1, 2, 3, 4]
 queries = [
                [1, 3],
                [1, 5]
           ]

Input 2:

 A = [1, 1, 1, 1]
 queries = [
                [1, 1],
                [1, 2],
                [1, 3],
                [2, 2],
                [2, 4],
                [3, 5]
           ]

Output 1:

 [3]

Output 2:

 [3, 3, 1]

Explanation 1:

 There is only one query.


Query 1:
 Set S = {3, 5}
 We must take subgraph formed by {3, 4, 5}. Therefore answer is 3.

Explanation 2:

 There are 3 queries.


Query 1:
 Set S = {1, 2, 3}
 If we just take these nodes, the subgraph is already connected and is minimal. Therefore answer is 3.

Query 2:
 Set S = {2, 4}
 We must take subgraph formed by {2, 1, 4}. Therefore answer is 3.

Query 3:
 Set S = {5}
 We just take node 5 here. Therefore answer is 1.