Answer k-step ancestor queries in a rooted tree
Company: Others
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a rooted tree encoded as a parent array `par[1..n]` where:
- Nodes are labeled `1..n`.
- `par[i]` is the parent of node `i`.
- Exactly one node has `par[i] = -1` (the root).
You must answer `q` queries. Each query provides a starting node `u` and an integer `k`.
Starting from `u`, apply the following operation **exactly `k` times** (or until you cannot move further):
- If the current node has a parent, move to its parent.
- If the current node is the root (parent is `-1`), you stay at the root for all remaining steps.
For each query, output the final node label after performing the moves.
### Input format
- `n`
- array `par[1..n]`
- `q`
- `q` lines: `u k`
### Output format
- For each query, one line with the final node label.
### Constraints (typical interview scale)
- `1 <= n, q <= 2 * 10^5`
- `0 <= k <= 10^9`
- `par[i] = -1` or `1 <= par[i] <= n`
### Example
If `par = [-1, 1, 1, 2, 2, 2, 2]` (meaning `par[1]=-1, par[2]=1, ...`):
- Query `(u=7, k=2)` goes `7 -> 2 -> 1`, output `1`.
- Query `(u=4, k=10)` ends at root `1`, output `1`.
Quick Answer: This question evaluates proficiency with tree data structures and ancestor-query algorithms, focusing on reasoning about parent arrays, upward traversal, and performance under large n and q constraints.
For each [u, k], return the node reached after moving to the parent k times, staying at the root if needed.
Constraints
- par is a 1-indexed parent array stored as a Python list where par[i-1] is node i parent.
- Exactly one parent is -1.
- Queries are [node, k] pairs.
Examples
Input: ([-1,1,1,2,2,2,2], [[7,2],[4,10],[3,0]])
Expected Output: [1, 1, 3]
Explanation: Queries climb ancestors and stay at root when k is too large.
Input: ([-1], [[1,5]])
Expected Output: [1]
Explanation: The root remains itself.
Input: ([2,-1,2,3], [[4,1],[4,2],[4,3]])
Expected Output: [3, 2, 2]
Explanation: A non-1 root is supported.
Hints
- Precompute binary lifting ancestors.
- If a jump goes above the root, return the root.