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