Redirecting to
NADOS

K'th Ancestor

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

You are given a tree of n nodes numbered from 0 to n-1 and is rooted at 0.
You are given an array parent of length n where parent[i] denotes parent of i'th node (in case of root it's parent is itself).

Now you have to answer q queries of format:
a k
answer to this query is k'th ancistor of node a if k'th ancistor does not exist simply print root.
In simple words you have to find k'th ancistor of a node.

Task: could u do it in log(n) or better time complexity.
Input Format 
n
p1
p2
p3
... n numbers till pn
q
a1 k1
a2 k2
... q queries till a(q) k(q)
Output Format 
for each query print in single line value of k'th ancistor
Question Video
Constraints 
1. 2 <= n <= 10^5
2. parent[0] = 0
3. 1 <= q <= 10^5
4. 0 <= a <= n-1
5. 1 <= k <= n
Sample Input 
7
0
0
0
1
3
2
3
6
5 1
6 2
3 2
3 3
6 3
4 1
Sample Output 
2
1
0
0
0
3


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name