---
title: "The LCA Problem"
summary: What the lowest common ancestor is, the seven distances it answers, and how to choose among four algorithms.
difficulty: core
tags: [trees, queries]
prereq: [trees/euler-tour, trees/dfs]
see: [lca/binary-lifting, lca/rmq-lca, lca/tarjan-offline, lca/virtual-tree]
---

:::definition label="LCA"
Root the tree at $r$. The **lowest common ancestor** $\operatorname{lca}(u,v)$ is the deepest vertex that is an ancestor of both. It is the unique vertex where the paths $r \to u$ and $r \to v$ stop agreeing, and the junction of the three paths $u$, $v$, $r$.
:::

:::props title="Everything one LCA answers"
- $\operatorname{dist}(u,v) = \operatorname{depth}(u) + \operatorname{depth}(v) - 2\operatorname{depth}(\operatorname{lca})$,
- $\operatorname{dist}$ on an **edge-weighted** tree: same formula with prefix sums from the root,
- the $k$-th vertex on the path $u \leadsto v$ (walk up from $u$, then from $v$ — @lca/binary-lifting),
- $\operatorname{lca}$ of a *set* $S$ (the "virtual tree" root) = the vertex minimising $\sum_{x \in S} \operatorname{dist}(x, y)$ over $S$'s Steiner closure — computed from $\operatorname{lca}$ of the min- and max-$\operatorname{tin}$ elements (@lca/virtual-tree),
- whether $u$ is an ancestor of $v$: $\operatorname{lca}(u,v) = u$, or the cheaper `tin`/`tout` test (@trees/euler-tour),
- "jump $j$ steps up from $v$", "the node just below the LCA on the path", "the centroid of a path",
- subtree-union queries: $\operatorname{lca}$ gives the boundary vertex, then a @structures/fenwick over `tin` gives the count.
:::

## Choosing an algorithm
| method | preprocess | query | memory | offline? | notes |
|---|---|---|---|---|---|
| naive climb | $O(n)$ | $O(n)$ worst | $O(n)$ | — | fine on balanced trees; a path graph kills it |
| **binary lifting** | $O(n \log n)$ | $O(\log n)$ | $O(n \log n)$ | no | the default; also does "jump $k$ steps" |
| Euler tour + sparse table | $O(n \log n)$ | $O(1)$ | $O(n \log n)$ | no | @lca/rmq-lca |
| Euler tour + ±1 RMQ (Bender–Farach-Colton) | $O(n)$ | $O(1)$ | $O(n)$ | no | @lca/rmq-lca, the "too clever" row |
| **Tarjan offline** | — | $O(n + q\,\alpha)$ total | $O(n+q)$ | **yes** | @lca/tarjan-offline; DSU only |
| Heavy-light | $O(n \log n)$ or $O(n)$ | $O(\log n)$ | $O(n)$ | no | pays off when you need path aggregates anyway (@advanced-tree/hld) |

:::note title="The honest recommendation"
Write binary lifting. It is 12 lines, never wrong, gives you $k$-th ancestor for free, and $O(n \log n)$ with $n = 2 \times 10^5$ is 3.6 million integers — 14 MB, well inside any limit. Move to $O(1)$ RMQ only when $q \ge 10^6$ and the constant actually shows up in the clock, or to Tarjan when the queries are offline and you already have DSU in the solution.
:::

## Two conventions that decide your code's shape
:::props title="Pick once, write in a comment"
- **root**: fix $r = 0$ (or 1) and never change it; "depth" is measured from it,
- **$\operatorname{lca}(v,v) = v$** — the identity case must be handled by the algorithm, not by an `if` at the call site,
- **0-indexed $\operatorname{up}[v][0] = \operatorname{parent}(v)$, with $\operatorname{parent}(r) = r$** (self-loop at the root) is the least error-prone: it makes lifting past the root idempotent instead of returning $-1$ that you must check everywhere,
- $\log$ bound: `LOG = __lg(n) + 1` (or 20 for $n \le 10^6$, 19 for $10^5$… compute it, don't guess),
- **forest**: if the input is not connected, LCA is undefined across components — either assert same-component with DSU first, or add a super-root (which makes every pair comparable and often simplifies the code).
:::

:::figure src="Simple_Rooted_Tree.svg" caption="A rooted tree: lca of the two deepest leaves is their branch point, and depth differences are what the lifting steps below measure."
:::