Binary Lifting

const LOG = 18; // log2(10^5) ≈ 17

function buildBinaryLifting(n, parent, root = 0) {
    const up = Array.from({length: n}, () => new Array(LOG).fill(-1));
    const depth = new Array(n).fill(0);

    // BFS to set parent and depth
    const queue = [root];
    const visited = new Array(n).fill(false);
    visited[root] = true;
    while (queue.length) {
        const v = queue.shift();
        up[v][0] = parent[v] ?? -1;
        for (let k = 1; k < LOG; k++) {
            if (up[v][k-1] !== -1) up[v][k] = up[up[v][k-1]][k-1];
        }
        for (const u of (adj[v] || [])) {
            if (!visited[u]) {
                visited[u] = true;
                depth[u] = depth[v] + 1;
                parent[u] = v;
                queue.push(u);
            }
        }
    }
    return { up, depth };
}

function kthAncestor(v, k, up) {
    for (let i = 0; i < LOG; i++) {
        if ((k >> i) & 1) {
            v = up[v][i];
            if (v === -1) return -1;
        }
    }
    return v;
}

function lca(u, v, up, depth) {
    if (depth[u] < depth[v]) [u, v] = [v, u];
    // Bring u to same depth as v
    u = kthAncestor(u, depth[u] - depth[v], up);
    if (u === v) return u;
    // Binary lift both until they diverge
    for (let k = LOG - 1; k >= 0; k--) {
        if (up[u][k] !== up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];
}