Lowest Common Ancestor

class LCA {
    constructor(n, edges, root = 0) {
        const LOG = Math.ceil(Math.log2(n + 1)) + 1;
        const adj = Array.from({length: n}, () => []);
        for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

        this.depth = new Array(n).fill(0);
        this.anc = Array.from({length: n}, () => new Array(LOG).fill(-1));

        // DFS to set depth and direct parent (anc[node][0])
        const stack = [[root, -1, 0]];
        while (stack.length) {
            const [u, p, d] = stack.pop();
            this.depth[u] = d;
            this.anc[u][0] = p >= 0 ? p : u; // root points to itself
            for (const v of adj[u]) if (v !== p) stack.push([v, u, d + 1]);
        }

        // Fill binary lifting table
        for (let j = 1; j < LOG; j++)
            for (let i = 0; i < n; i++)
                this.anc[i][j] = this.anc[this.anc[i][j-1]][j-1];

        this.LOG = LOG;
    }

    query(u, v) {
        // Bring to same depth
        if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
        let diff = this.depth[u] - this.depth[v];
        for (let j = 0; diff; j++, diff >>= 1) if (diff & 1) u = this.anc[u][j];
        if (u === v) return u;
        // Lift together until just below LCA
        for (let j = this.LOG - 1; j >= 0; j--)
            if (this.anc[u][j] !== this.anc[v][j]) { u = this.anc[u][j]; v = this.anc[v][j]; }
        return this.anc[u][0];
    }

    distance(u, v) {
        return this.depth[u] + this.depth[v] - 2 * this.depth[this.query(u, v)];
    }
}