LCA Binary Lifting Build

Problem

Build a binary lifting table for a tree with n nodes rooted at root, then answer lowest-common-ancestor queries.

parent[k][v] is the 2^k-th ancestor of v. Lift the deeper node by depth difference, then raise both nodes together while their ancestors differ. Return the LCA for each [a, b] query in order. edges is a list of [u, v] pairs.

Hint

Binary lifting reduces each LCA query to O(log n) ancestor jumps.

Test cases

case 1

in: [5,[[0,1],[0,2],[1,3],[1,4]],0,[[3,4],[3,2],[1,2],[0,4]]]

expected: [1,0,0,0]

case 2

in: [3,[[0,1],[1,2]],0,[[0,2],[2,2]]]

expected: [0,2]

case 3

in: [3,[[0,1],[0,2]],0,[[1,2]]]

expected: [0]

case 4

in: [1,[],0,[[0,0]]]

expected: [0]

Starter codePython

def lca_binary_lifting(n, edges, root, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor