LCA Solution

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.