Chain of Command

An organization is made up of n people. The organizational structure can be represented as a tree, with each person representing a node in the tree. All but the root node has a single parent, representing the node's upstream reporting line. A node may have zero or more children, representing those people who report into them.
If person 1 is the root of the tree, we can represent this structure in an array parent, where parent[i] represents the parent of node i + 1. Note that parent[0] = -1 to indicate no parent.
Within this organization, directives may be issued from a person to all people reporting into them, including all descendants in the tree. These directives propagate as follows:
A person sends the directive to its direct child nodes in ascending order of their indices.
If a node has more than one child, the node waits for propagation to complete fully to each child's subtree before issuing the directive to the next child.
Each child node propagates the directive to its subtree using the same process.
The propagation stops when all nodes in the subtree have received the directive.
For a single directive, determine who was the kth person to receive it. This query can be modeled as a tuple [startNode, k], where startNode is the person issuing the directive.
If k is greater than the total number of people receiving the directive, including direct reports and descendants of their direct reports, return -1 to indicate that no kth person exists.
For a given organization, evaluate all queries independently and return an integer array whose element at each position is the answer to the corresponding query.

Function
chainOfCommand(parent: int[], queries: int[][]) → int[]

Examples
Example 1
parent = [-1, 1, 1, 1, 3, 5, 3, 5, 7]
queries = [[1, 5], [7, 2], [9, 2], [3, 6]]
return = [6, 9, -1, 9]
The array parent represents the tree shown in the source. If person 1 issues a directive, people receive it in the following order: [1, 2, 3, 5, 6, 8, 7, 9, 4].
If person 3 issues a directive, people receive it in the following order: [3, 5, 6, 8, 7, 9].
If person 7 issues a directive, people receive it in the following order: [7, 9].
If person 9 issues a directive, people receive it in the following order: [9].
Processing the queries:
queries[0] = [1, 5]: if person 1 issues a directive, the 5th person receiving it would be 6.
queries[1] = [7, 2]: if person 7 issues a directive, the 2nd person receiving it would be 9.
queries[2] = [9, 2]: if person 9 issues a directive, there is no 2nd person to receive it.
queries[3] = [3, 6]: if person 3 issues a directive, the 6th person receiving it would be 9.
Hence, the array returned is [6, 9, -1, 9].
Example 2
parent = [-1, 1, 1, 2, 2]
queries = [[1, 3], [2, 3]]
return = [4, 5]
If person 1 issues a directive, people receive it in the following order: [1, 2, 4, 5, 3].
If person 2 issues a directive, people receive it in the following order: [2, 4, 5].
For queries[0] = [1, 3], the 3rd person to receive the directive is person 4. For queries[1] = [2, 3], the 3rd person to receive the directive is person 5.
Hence, the array returned is [4, 5].

Constraints
2 <= n <= 10^5
1 <= parent[i] <= n for all nodes except the root node, where parent[0] = -1
1 <= q <= 2 * 10^5
1 <= queries[i][0] <= n
1 <= queries[i][1] <= n

The trick is one preorder DFS from the root, children sorted ascending, recording each node's entry index tin[v] and subtree size sz[v]. The order for any startNode is exactly the contiguous slice of the global preorder starting at tin[start] with length sz[start]. So the kth person is order[tin[start] + k - 1], valid only if k <= sz[start], otherwise -1. Every query becomes O(1) after O(n) preprocessing. Pitfalls: recursing on 10^5 nodes can overflow the stack in some languages, so go iterative. Build the children lists by looping i from 2 to n, which already gives ascending order, no sorting needed. Watch the off-by-one between 0-indexed parent and 1-indexed people. Also don't assume the root is always person 1 without using parent[0] = -1. If the indexing trips you up live, StealthCoder is the hedge that gives you a clean iterative version.

The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.