---
title: "Tarjan's Offline LCA"
summary: Answer all LCA queries in near-linear time with a DFS and a disjoint-set union — no log factor, no table.
difficulty: hard
tags: [dsu, offline, queries]
time: n + q alpha
space: n + q
prereq: [lca/problem, structures/dsu]
see: [structures/dsu, lca/binary-lifting]
---

:::definition label="Offline"
"All queries are known in advance and may be reordered." That licence is what makes this algorithm possible — and what makes it useless when a query depends on an earlier answer, or when vertices are added one by one.
:::

:::theorem title="Tarjan's algorithm"
Run a DFS. When a vertex $v$ finishes, mark it **black** and union it with each black child, setting the child set's representative to $v$. For every query $(v, u)$ with $u$ already black, the answer is $\operatorname{find}(u)$.
:::

:::proof
When $v$ is finishing and $u$ is black, $u$ lies entirely inside the finished part of the tree, and the union chain has pulled every black vertex whose "first not-yet-finished ancestor" is $a = \operatorname{lca}(u,v)$ into $a$'s set: a vertex is unioned upward exactly when its own DFS finishes, so it stops at the highest ancestor that is still open — and $a$ is still open (it is an ancestor of $v$), while everything on the $u$ path below $a$ is closed. No vertex outside $a$'s subtree is in the set, since such a vertex would have had to be unioned through an ancestor of $a$, which is not yet finished. So $\operatorname{find}(u) = a$. ∎
:::

```cpp tarjan-lca.cpp
vector<vector<pair<int,int>>> adj(n);        // neighbours, tree
vector<vector<pair<int,int>>> qs(n);         // qs[v] = {(other, query id)}
vector<int> dsu(n), anc(n), state(n);        // state: 0 white, 1 grey, 2 black
vector<int> ans(q);
int find(int v) { return dsu[v] == v ? v : dsu[v] = find(dsu[v]); }
void dfs(int v) {
    state[v] = 1; anc[v] = dsu[v] = v;
    for (int to : adj[v]) if (state[to] == 0) {
        dfs(to);
        dsu[find(to)] = v; anc[find(v)] = v;   // pull the child set up to v
    }
    state[v] = 2;                              // black
    for (auto [to, id] : qs[v])
        if (state[to] == 2) ans[id] = anc[find(to)];
}
```

:::warning title="The one line that breaks people"
`anc[find(v)] = v;` must be written **after** `dsu[find(to)] = v;`, and it must use `find(v)` — the representative *after* the merge. The `anc` array is the actual answer payload: `dsu` alone only tracks sets, and $\operatorname{find}$ returns an arbitrary member. Forgetting the `anc` update gives answers that are correct on stars and wrong on paths, which is the worst kind of bug.
:::

:::props title="Complexity and why it is near-linear"
- $O(n + q)$ DFS work plus $O((n+q)\,\alpha(n))$ for the $\operatorname{find}$ calls: each tree edge causes one union, each query causes at most two finds,
- with union by size/rank the inverse-Ackermann factor is a constant ≤ 4 for any real $n$,
- memory $O(n + q)$: no $\log n$ table (compare @lca/binary-lifting's $n \log n$),
- stack depth $n$: iterative version or `pthread` for $n = 10^6$ (@foundations/walks).
:::

:::example title="When offline wins outright"
"$n,q \le 2\times 10^6$", memory 64 MB, and each query is `dist(u,v)`. Binary lifting needs $2\times 10^6 \times 21 \times 4\,\text{B} = 168$ MB — over the limit. Tarjan needs `dsu + anc + state + depth + tin` ≈ 40 MB and answers all queries in one pass. This is not hypothetical: it is the standard intended difference on such problems, and the offline constraint is *forced* on you by memory, not stated in the problem.
:::

:::note title="Generalising the trick"
The pattern "answer queries at the moment a vertex finishes, using the DSU state of closed subtrees" is **Tarjan's offline framework**, and it also solves: closest-pair-of-marked-nodes per subtree, "for each query vertex, the nearest ancestor satisfying P" (with a stack instead of DSU), and the offline version of "smallest subtree containing all query vertices" (@lca/virtual-tree). Whenever a query's answer is determined by an *ancestor relationship* and everything relevant is already closed, offline DSU beats any table.
:::

:::problems
- [[CSES 2079]] Finding a Centroid | https://cses.fi/problemset/task/2079 | easy | the answer is decided at finish time — one DFS, no table
- [[CSES 1135]] Distance Queries | https://cses.fi/problemset/task/1135 | core | re-solve it offline: one DFS + DSU instead of a lifting table
:::