959. Lowest Common Ancestor Using Binary Lifting

Given a tree with n nodes labeled 0..n-1 rooted at node 0, described by an undirected edge list, answer a batch of queries: for each pair [u, v], return the label of their lowest common ancestor. Use binary lifting (or ancestor jumping). Return the answers as an array in order. The input is JSON {n, edges, queries}.

Input: JSON {n, edges, queries}.

Output: Array — the LCA label for each query.

Examples

Input: {"n":7,"edges":[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],"queries":[[3,4],[3,5],[6,6]]}
Output: [1,0,6]
Explanation: LCA of each pair.

Input: {"n":1,"edges":[],"queries":[[0,0]]}
Output: [0]
Explanation: Only the root.

Input: {"n":3,"edges":[[0,1],[0,2]],"queries":[[1,2]]}
Output: [0]
Explanation: Root is the LCA.

Constraints

• 1<=n<=10^5
• edges form a tree rooted at 0
• 1<=queries<=10^5

Asked by