class LCA:
def __init__(self, adj, root):
self.euler, self.depth, self.first = self.eulerTour(adj, root)
self.st = self.buildSparseTable()
def eulerTour(self, adj, root):
# ... as shown before
def buildSparseTable(self):
# Build on (depth, euler_index) pairs
# Query returns index of minimum depth
# ...
def query(self, u, v):
i, j = self.first[u], self.first[v]
if i > j:
i, j = j, i
# Query for minimum depth index in [i, j]
min_idx = self.rangeMinIndex(i, j)
return self.euler[min_idx]
The sparse table should track both the minimum depth and its index, or build on indices and compare depths.