547. Ancestor Queries
A company's reporting structure has n employees numbered 0 to n - 1, where employee 0 is the chief executive. The array edges lists the n - 1 reporting links as undirected pairs [u, v], joining a manager and one of their direct reports in either order; the links form a tree.
For two employees, the closest shared manager is the employee who is farthest from the CEO and who lies on the reporting chain (up to the CEO) of both of them; an employee counts as lying on their own chain. Given queries, where each queries[i] = [x, y], return an array answer in which answer[i] is the closest shared manager of x and y.
Example 1
- Input:
- n = 9edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7],[7,8]]queries = [[3,4],[6,8],[4,2],[7,7],[8,0]]
- Output:
- [1,5,0,7,0]
- Explanation:
3 and 4 meet at 1; 6 and 8 meet at 5; 4 and 2 meet at the root 0; a node paired with itself is its own meeting point; and pairing with the root always gives the root.
Example 2
- Input:
- n = 3, edges = [[1,0],[2,1]], queries = [[2,1],[2,0]]
- Output:
- [1,0]
- Explanation:
The chain is 0-1-2; node 1 is an ancestor of node 2, and node 0 is an ancestor of both.
Constraints
1 ≤ n ≤ 105
1 ≤ queries.length ≤ 105
edges.length == n - 1, 0 ≤ u, v < n; the edges form a tree, which is rooted at node 0
0 ≤ x, y < n (the two employees in a query may be equal)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n log n)