Coding questions · Others

Answer ancestor-walk queries on a rooted tree

This question evaluates understanding of tree data structures and ancestor-walk queries, assessing competency in traversing rooted trees, interpreting parent arrays, and designing efficient query-processing methods for large n and q.

Problem (Tree / Parent Array Queries)

You are given a rooted tree with n nodes labeled 1..n, represented by a parent array par[1..n]:

par[i] is the parent of node i
par[root] = -1
The input guarantees this forms a valid rooted tree (exactly one root, no cycles).

Example:

par = [-1, 1, 1, 2, 2, 2, 2] (meaning par[1] = -1, par[2] = 1, …)

You will be given q queries. Each query provides:

a starting node u
an integer k ≥ 0 (“number of commands/steps”)

For each query, start at node u and move to the parent exactly k times (or until you reach the root). If you reach the root before using all steps, you remain at the root.

Output

For each query, output the label of the final node where you stop.

Constraints (assume large input)

Design an approach efficient for large n, q (e.g., up to 2e5).

Ancestor Walk Queries

Hints

Clarify edge cases before coding.
Keep the return value deterministic.