Find k-th recipient in command propagation order

Chain of Command (k-th Receiver in DFS-by-Child-Id Order)

A company org chart forms a rooted tree with n people (nodes), labeled 1..n.

You are given an array parent[1..n] describing the tree:

• parent[i] = -1 means i is the root (top leader)
• otherwise, parent[i] is the direct manager (parent) of person i
• each node has zero or more direct reports (children)

Command propagation rule

When a person u issues a command, it is sent to all subordinates of u (all descendants of u), using this strict order:

1. Consider u ’s direct children, sorted by increasing person id.
2. Send the command to the smallest-id child first.
3. Before sending to the next child, the command must be fully propagated throughout the current child’s entire subtree using the same rule .

This defines a deterministic traversal order over the descendants of u:

• It is equivalent to a DFS preorder over u ’s subtree excluding u , where children are visited in ascending id.

Task

Given:

• parent[1..n]
• an issuer u
• an integer k (1-indexed)

Return the person id of the k-th subordinate who receives the command in the propagation order.

If u has fewer than k descendants, return -1.

Input/Output

• Input: parent[] , u , k
• Output: the person id of the k-th recipient, or -1

Notes / Assumptions

• The input forms a valid tree (exactly one root).
• k is 1-indexed over recipients (descendants only; the issuer u is not counted).
• Constraints may be large (e.g., n up to 2e5), so an approach better than simulating propagation step-by-step for each query is typically expected (if multiple queries are present, state how many).