2007. The kth Ancestor, Answered Fast
A rooted tree has n nodes numbered 1 to n, with node 1 as the root. For each
node from 2 to n its parent is given. Then q questions arrive, each a node
u and a number k: print the kth ancestor of u, or 0 if walking up k
steps leaves the tree.
The 1st ancestor is the parent, the 2nd is the grandparent, and the 0th ancestor of a node is the node itself.
``` parents: 2->1 3->1 4->2 5->2
4 with k = 1 -> 2 4 with k = 2 -> 1 4 with k = 3 -> 0 the walk runs off the root ```
## What most people try first
Walk up one parent at a time. Each question costs the depth, so a path-shaped
tree of 2 * 10^5 nodes with 2 * 10^5 questions is 4 * 10^10 steps. The
tree does not have to be adversarial for this to bite: any long chain does it.
## Precompute the jumps that are powers of two
Let up[j][v] be the ancestor exactly 2^j steps above v. The table builds
itself, because a jump of 2^j is two jumps of 2^(j-1):
up[0][v] = parent of v
up[j][v] = up[j-1][ up[j-1][v] ]
Any k is a sum of distinct powers of two, which is exactly its binary
representation, so take one jump per set bit:
for each bit b set in k: v = up[b][v]
## Why running off the root costs nothing
Give the root parent 0, and let node 0 be its own parent. Then every jump
from 0 stays at 0, so a walk that leaves the tree lands on 0 and remains
there for the rest of the jumps.
That is why 0 is chosen rather than a sentinel like -1: no bounds test is
needed anywhere in the loop, and the answer for "no such ancestor" falls out of
the same arithmetic as every other answer.
## Cost
Building is O(n log n), about 3.6 * 10^6 table entries at n = 2 * 10^5,
which is also the memory. Each question is O(log n), at most 18 jumps.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - the parent of node `i` is strictly less than `i`, so the input is always a tree rooted at node 1 - `1 ≤ u ≤ n` - `0 ≤ k ≤ n`
Input
The first line contains two integers n and q.
If n is greater than 1, the second line contains n - 1 integers: the parent of node 2, then of node 3, up to node n.
Each of the next q lines contains two integers u and k.
Output
Print one integer on its own line for each question: the kth ancestor of u, or 0 if there is no such ancestor because the walk leaves the tree.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.