Lowest common ancestor queries
Your task
You are given a rooted tree with n nodes labeled 0..n-1 as a parent array, where parent[i] is the parent of node i and parent[r] == -1 for the unique root r. Answer a batch of LCA queries: for each [u, v] return the label of their lowest common ancestor. Preprocess so each query is answered in O(log n). Return the list of answers in query order.
Examples
lca_binary_lifting(n: int, parent: list[int], queries: list[list[int]]) -> list[int]Example 1
Input
lca_binary_lifting(7, [-1, 0, 0, 0, 1, 1, 3], [[4, 5], [4, 2], [6, 4], [6, 3], [0, 6], [5, 5]])Output
[1, 0, 0, 3, 0, 5]