Offline LCA

function tarjanLCA(n, edges, queries) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }

    // Group queries by node
    const queryList = Array.from({length: n}, () => []);
    for (let i = 0; i < queries.length; i++) {
        const [u, v] = queries[i];
        queryList[u].push([v, i]);
        queryList[v].push([u, i]);
    }

    const parent = Array.from({length: n}, (_, i) => i);
    const find = x => parent[x] === x ? x : (parent[x] = find(parent[x]));
    const visited = new Array(n).fill(false);
    const answers = new Array(queries.length);
    const ancestor = Array.from({length: n}, (_, i) => i);

    function dfs(u, p) {
        ancestor[u] = u;
        for (const v of adj[u]) {
            if (v === p) continue;
            dfs(v, u);
            // Union v into u's component, ancestor of root = u
            parent[find(v)] = u;
            ancestor[find(u)] = u;
        }
        visited[u] = true;
        for (const [v, qi] of queryList[u]) {
            if (visited[v]) {
                answers[qi] = ancestor[find(v)];
            }
        }
    }

    dfs(0, -1);
    return answers;
}