LCA Binary Lifting Step Count

Problem

Count the ancestor jumps the binary lifting LCA algorithm makes for each query.

After building the 2^k ancestor table, equalize depths bit by bit, raise both nodes together from the highest level down while their ancestors differ, and finish with one final parent jump. Count every single table jump, including the final one. Return the step count for each [a, b] query. edges is a list of [u, v] pairs and root is the tree root.

Hint

The algorithm performs at most 2*log2(n) jumps because every jump moves a node up by a power of two.

Test cases

case 1

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

expected: [2,1,1,0]

case 2

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

expected: [1,1]

case 3

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

expected: [1,1]

case 4

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

expected: [1]

Starter codePython

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

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