0

Ninja And Numbers

Difficulty: MEDIUM
Avg. time to solve
40 min
Success Rate
60%

Problem Statement

Ninja is learning tree data structures. His friend is helping him learn by giving him problems to solve. He gives him a tree with N nodes numbered from 0 to N - 1 in the form of a parent array parent where parent[i] is the parent of the ith node. The root of the tree is node 0. Now Ninja has to find the kth ancestor of a given node. The kth ancestor of a tree node is the kth node in the path from that node to the root node.

Input Format:
The first line of input contains a single integer ‘T’, denoting the number of test cases.

The second line of each test case contains a positive integer ‘N’, denoting the number of nodes.

The third line of each test case contains the parent array.

The fourth line of each test case contains a node value and k value.
Output Format :
The first and only line of each test case contains an integer denoting the kth ancestor.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function. 
Constraints:
1 <= T <= 10
1 <= k <= N <= 5 * 10 ^ 4
0 <= node < N
0 <= parent[i] < N

Time limit: 1 second
Sample Input 1:
2
7
-1 0 0 1 1 2 2
3 1
7
-1 0 0 1 1 2 2
5 2
Sample Output 1:
1
0
Explanation for Sample Output 1:

1

In the first test case, it is visible from the figure that the 1st ancestor of a node with the value of 3 is the parent node of 3. Parent of 3 is 1.So we return 1 as our answer. 

In the second test case, the first ancestor of the node with the value 5 is 2. Now to find the 2nd ancestor of this node, we find the 1st ancestor of the parent of this node. Now, 1st ancestor of 2 is 0. So we return 0 as our answer
Sample Input 2:
2
7
-1 0 0 1 1 2 2
4 2
7
-1 0 0 1 1 2 2
6 1
Sample Output 2:
 0
 2
Reset Code
Full screen
copy-code
Console