Lowest Common Ancestor

The LCA of $u$ and $v$ in a rooted tree is the deepest vertex that is an ancestor of both. It is the single most reused tree primitive — path queries, distances, and virtual trees all rest on it.

Method comparison

Method	Preprocess	Query	Notes
Naive climbing	$O(n)$	$O(n)$	fine for tiny trees
Binary lifting	$O(n\log n)$	$O(\log n)$	the default — also gives $k$-th ancestor and path aggregates
Euler tour + sparse table	$O(n\log n)$	$O(1)$	best constant when you only need LCA
Tarjan offline	$O((n+q)\alpha )$	amortized	needs all queries up front
Farach-Colton-Bender	$O(n)$	$O(1)$	optimal, large constant
HLD	$O(n)$	$O(\log n)$	free if you already built HLD
Link-cut tree	$O(n)$	$O(\log n)$ am.	when the tree changes

Binary lifting

const int LOG = 20;
vector<array<int, LOG>> up;
vector<int> depth;
 
void dfs(int u, int p) {
    up[u][0] = (p == -1 ? u : p);
    for (int k = 1; k < LOG; k++) up[u][k] = up[up[u][k-1]][k-1];
    for (int v : adj[u]) if (v != p) { depth[v] = depth[u] + 1; dfs(v, u); }
}
 
int kthAncestor(int u, int k) {
    for (int i = 0; i < LOG; i++) if (k >> i & 1) u = up[u][i];
    return u;
}
 
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    u = kthAncestor(u, depth[u] - depth[v]);
    if (u == v) return u;
    for (int 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];
}

The jump loop goes downward in $k$ and moves only when the ancestors differ — that lands both pointers on the children of the LCA. Jumping when they are equal would overshoot.

Euler tour + sparse table — $O(1)$ queries

Record the depth at each of the $2n-1$ visits of an Euler tour. $\mathrm{LCA}(u,v)$ is the minimum-depth entry between the first occurrences of $u$ and $v$ — a range minimum query.

vector<int> euler, firstOcc, dep;
 
void dfs(int u, int p, int d) {
    firstOcc[u] = euler.size();
    euler.push_back(u); dep.push_back(d);
    for (int v : adj[u]) if (v != p) {
        dfs(v, u, d + 1);
        euler.push_back(u); dep.push_back(d);      // re-visit on return
    }
}
// then a sparse table over dep[], returning the index of the minimum

Shorter to write than it looks, and the constant factor beats binary lifting when $q$ is large.

What LCA unlocks

Task	Formula
Distance	$d_u+d_v-2d_{\mathrm{lca}}$
Is $u$ an ancestor of $v$?	$\mathrm{tin}[u]\le \mathrm{tin}[v]$ and $\mathrm{tout}[v]\le \mathrm{tout}[u]$ — no LCA needed
Is $w$ on the path $u\to v$?	$\mathrm{dist}(u,w)+\mathrm{dist}(w,v)=\mathrm{dist}(u,v)$
Path max/min/sum	binary lifting with an aggregate array, or HLD
Path updates	HLD + lazy segment tree, or difference-on-tree
$k$-th vertex on a path	jump $k$ from $u$, or $\mathrm{dist}-k$ from $v$
Meeting point of three vertices	the vertex among $\mathrm{lca}(u,v),\mathrm{lca}(v,w),\mathrm{lca}(u,w)$ that is deepest — exactly two of the three coincide
Virtual tree	sort by tin, insert consecutive LCAs

Path updates without HLD

For additive path updates with a single query at the end, skip HLD entirely: add $+x$ at $u$ and $v$, and $-x$ at $\mathrm{lca}$ and $-x$ at $\mathrm{parent}(\mathrm{lca})$, then take subtree sums in one DFS. $O(\log n)$ per update, $O(n)$ to finalise. This “difference array on a tree” trick is far simpler than HLD and covers a surprising number of problems.

See also: Binary Lifting · Euler Tour · HLD