LCA Euler Tour Sparse Table

Problem

Answer lowest-common-ancestor queries with an Euler tour plus a sparse table.

Record the Euler walk of a tree rooted at root (each edge adds one entry), build a sparse table over the walk keyed by node depth, and query the minimum-depth node between the two first-occurrence positions. Return the LCA for each [a, b] query in order. edges is a list of [u, v] pairs.

Hint

The LCA of two nodes is the shallowest node appearing between their first occurrences in the Euler walk.

Test cases

case 1

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

expected: [0,1,0,1]

case 2

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

expected: [1,0,0]

case 3

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

expected: [1,2]

case 4

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

expected: [0]

Starter codePython

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

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