K-th Ancestor Subtree Preorder Query
Adobe● HardFULLTIMEOAProblem statement
You are given a tree with nodes numbered from 1 to n. Node i stores values[i - 1]. The tree is rooted at node 1.
The undirected edges are processed in their given order. After rooting the tree, each node's children are visited in the order in which their incident edges first appear in edges.
For each query [u, k]:
- Find the
k-th ancestor of nodeu, where the0-th ancestor isuitself. - If that ancestor does not exist, return the one-element row
[-1]. - Otherwise, return the values in that ancestor's subtree in preorder.
Return one result row for each query, preserving query order.
Function
subtreeValuesAfterAncestor(values: int[], edges: int[][], queries: int[][]) → int[][]Examples
Example 1
values = [10, 20, 30, 40, 50]edges = [[1, 2], [1, 3], [2, 4], [2, 5]]queries = [[4, 1], [4, 2], [3, 0], [1, 1]]return = [[20, 40, 50], [10, 20, 40, 50, 30], [30], [-1]]The first query reaches node 2 and returns its preorder subtree. The second reaches root 1. The third keeps node 3, and the root has no first ancestor for the last query.
Example 2
values = [1, 2, 3, 4]edges = [[2, 4], [1, 3], [1, 2]]queries = [[4, 1], [4, 2]]return = [[2, 4], [1, 3, 2, 4]]Node 1 visits child 3 before child 2 because edge [1, 3] appears earlier than [1, 2]. Node 2 then visits node 4.
Constraints
1 <= n == values.length <= 2 * 10^5-10^9 <= values[i] <= 10^9edges.length == n - 1edgesdescribes one valid tree on nodes1throughn.1 <= queries.length <= 2 * 10^51 <= u <= n0 <= k <= n- The total number of values returned across all successful queries is at most
2 * 10^5.