Answer ancestor-walk queries on a rooted tree
Problem: Ancestor-Walk Queries on a Rooted Tree
You are given a rooted tree with n nodes, labeled 1 through n. The tree structure is defined by a parent array, par[1..n], where par[i] denotes the parent of node i. The root node is identified by par[root] = -1. The input guarantees that this array always forms a valid rooted tree, meaning there is exactly one root and no cycles.
Example:
par = [-1, 1, 1, 2, 2, 2, 2]
(This implies par[1] = -1 (node 1 is the root), par[2] = 1, par[3] = 1, par[4] = 2, par[5] = 2, par[6] = 2, par[7] = 2).
You will then receive q queries. Each query consists of:
- A starting node
u. - An integer
k ≥ 0, representing the number of steps to move upwards.
For each query, you must start at node u and repeatedly move to its parent exactly k times. If you reach the root node before completing all k steps, you remain at the root for the rest of the steps.
Output
For each query, your task is to output the label of the final node where you stop.
Constraints
Design an approach that is efficient for large inputs, where n and q can be up to 2e5.
AI interview prep
Core dilemma
The central engineering conflict is balancing the precomputation time and space required to build an efficient lookup structure against the query time for each of the `q` ancestor-walk requests, especially given large `n` and `q`. A naive O(k) per query solution will be too slow.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Answer ancestor-walk queries on a rooted tree
Problem: Ancestor-Walk Queries on a Rooted Tree
You are given a rooted tree with n nodes, labeled 1 through n. The tree structure is defined by a parent array, par[1..n], where par[i] denotes the parent of node i. The root node is identified by par[root] = -1. The input guarantees that this array always forms a valid rooted tree, meaning there is exactly one root and no cycles.
Example:
par = [-1, 1, 1, 2, 2, 2, 2]
(This implies par[1] = -1 (node 1 is the root), par[2] = 1, par[3] = 1, par[4] = 2, par[5] = 2, par[6] = 2, par[7] = 2).
You will then receive q queries. Each query consists of:
- A starting node
u. - An integer
k ≥ 0, representing the number of steps to move upwards.
For each query, you must start at node u and repeatedly move to its parent exactly k times. If you reach the root node before completing all k steps, you remain at the root for the rest of the steps.
Output
For each query, your task is to output the label of the final node where you stop.
Constraints
Design an approach that is efficient for large inputs, where n and q can be up to 2e5.