# K'th Ancestor

#### 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 kanswer 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
`np1p2p3... n numbers till pnqa1 k1a2 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^52. parent[0] = 03. 1 <= q <= 10^54. 0 <= a <= n-15. 1 <= k <= n`
Sample Input
`7000132365 16 23 23 36 34 1`
Sample Output
`210003`

• Related Topics

Run

Run
Id Name