InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Queries On A Tree

Problem Description

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.

Problem Constraints

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

Input Format

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.

Output Format

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

Example Input

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]

Example Output

Output 1:


Output 2:

 [3, 3, 1]

Example Explanation

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.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Queries On A Tree on Interview Code Editor
  • Hint 1
  • Solution Approach
  • Complete Solution


Click here to start solving coding interview questions