iii. Lowest Common Ancestor

The deepest common ancestor of $u$ and $v$. Distances, path aggregates, path intersections, virtual trees and most path problems reduce to it.

Method	Build	Query	Use
naive climbing	$O(n)$	$O(n)$	fine for tiny trees or a handful of queries
binary lifting	$O(n\log n)$	$O(\log n)$	default: also $k$-th ancestor and path aggregates
DFS order + sparse table	$O(n\log n)$	$O(1)$	many LCA queries; beats binary lifting’s constant when $q$ is large
Tarjan offline (DSU)	$O((n+q)\alpha )$	—	all queries known
Schieber–Vishkin	$O(n)$	$O(1)$	bit tricks, small memory
Farach-Colton–Bender	$O(n)$	$O(1)$	optimal RMQ-based variant; large constant, rarely worth it over Schieber–Vishkin
HLD	$O(n)$	$O(\log n)$	free if HLD is built anyway
link-cut tree	$O(n)$	$O(\log n)$ amortized	only when the tree itself changes online
ladder + jump pointers	$O(n\log n)$	$O(1)$ level ancestor	$k$-th ancestor in $O(1)$

Binary lifting with path aggregates

template <class T = ll, class Op = plus<T>> struct BinaryLifting {
    int n, lg = 1; Op op; T e; vector<vector<pair<int, T>>> adj; vector<int> dep;
    vector<vector<int>> up; vector<vector<T>> agg;          // up[k][v]: 2^k-th ancestor (root -> root); agg: op over those edges
    BinaryLifting(int n, Op f = Op(), T id = T()) : n(n), op(f), e(id), adj(n), dep(n) { while ((1 << lg) < n) lg++; }
    void addEdge(int u, int v, T w = T(1)) { adj[u].push_back({v, w}), adj[v].push_back({u, w}); }
    void build(int root = 0) {
        up.assign(lg, vector<int>(n, root)); agg.assign(lg, vector<T>(n, e)); vector<int> order{root}; dep[root] = 0;
        for (int i = 0; i < sz(order); i++) { int u = order[i]; for (auto [v, w] : adj[u]) if (v != up[0][u] && v != root) up[0][v] = u, agg[0][v] = w, dep[v] = dep[u] + 1, order.push_back(v); }
        for (int k = 1; k < lg; k++) for (int v : order) { int m = up[k - 1][v]; up[k][v] = up[k - 1][m]; agg[k][v] = op(agg[k - 1][v], agg[k - 1][m]); }
    }
    int jump(int u, int k) const { if (k < 0 || k > dep[u]) return -1; for (int i = 0; k; i++, k >>= 1) if (k & 1) u = up[i][u]; return u; }
    int lca(int u, int v) const {
        if (dep[u] < dep[v]) swap(u, v);
        u = jump(u, dep[u] - dep[v]); if (u == v) return u;
        for (int k = lg - 1; k >= 0; k--) if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
        return up[0][u];
    }
    int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
    T query(int u, int v) const {                           // op over the edges of the path u - v
        T res = e; if (dep[u] < dep[v]) swap(u, v);
        for (int k = lg - 1; k >= 0; k--) if (dep[u] - (1 << k) >= dep[v]) res = op(res, agg[k][u]), u = up[k][u];
        if (u == v) return res;
        for (int k = lg - 1; k >= 0; k--) if (up[k][u] != up[k][v]) res = op(res, op(agg[k][u], agg[k][v])), u = up[k][u], v = up[k][v];
        return op(res, op(agg[0][u], agg[0][v]));
    }
};

The aggregate needs to be associative and commutative here (max, min, sum, gcd, xor); for non-commutative ones (matrix products, “path as a sequence”) keep upward and downward versions separately.

Non-invertible aggregates

Prefix subtraction works for sums (f(u) - f(lca)-style tricks), but max, min and gcd do not invert: there is no way to recover “the max over this sub-range” by subtracting a prefix max. Always climb explicitly from both endpoints to the LCA and combine as query does above, rather than trying to shortcut with a difference.

Memory: $O(n\log n)$ integers — for $n=10^6$ and $\text{LOG}=20$ that’s 80 MB of int, often too much. Reduce LOG to $\lceil {\log }_{2}n\rceil$ exactly, switch to the Euler-tour method below if only plain LCA is needed, or use HLD (which is $O(n)$ memory).

The same table on any functional graph answers “where after $10^{18}$ steps” (Functional Graphs) — the only requirement is a single “next” pointer, not a tree:

Application	up[v][0] is
tree ancestor	parent
permutation power	$\sigma (v)$
successor / “next greater” chains	next index
game state after $k$ moves	the forced move
sparse table over an array	”jump to the first index outside the current window”

The last row is the basis of the classic “minimum number of intervals to cover a range”: precompute for each position the farthest reachable position with one interval, then binary lift to answer coverage queries in $O(\log n)$.

Proof: binary lifting

up[k][v] is correct by induction on $k$ (two jumps of $2^{k-1}$), saturating at the root. jump decomposes $k$ into powers of two. In lca, after equalising depths, $u=v$ means one was an ancestor of the other. Otherwise the invariant ”$u\ne v$, same depth, LCA strictly above them” holds; for decreasing $k$, the $2^k$-th ancestors differ iff they are below the LCA, so jumping exactly then moves both to the highest pair of distinct ancestors, i.e. the children of the LCA on the two branches (any remaining gap would be a sum of smaller powers already tried). query performs the same moves and combines exactly the edges walked over.

$O(1)$ LCA with a sparse table on DFS order

In preorder, for $u\ne v$ with $\text{tin}(u)<\text{tin}(v)$: let $w$ be the vertex of minimum depth among positions $(\text{tin}(u),\text{tin}(v)]$; then $\text{LCA}(u,v)=\text{parent}(w)$. Uses $n$ entries instead of the $2n-1$ of the Euler tour. $O(1)$ LCA is also the standard prerequisite for virtual trees: it is what lets the pairwise LCAs of $k$ marked vertices be found fast enough to build the virtual tree in $O(k\log n)$.

Three different “Euler tour” flattenings show up across this chapter, easy to conflate: (A) the size-$n$ preorder subtree tour used here and for subtree updates/queries (Euler Tour, Subtree and Path Queries, Fenwick/segment tree); (B) the size-$2n$ entry/exit path tour, for path sum/XOR and Mo’s on trees (same note, Fenwick with an inverse op); (C) this note’s size-$(2n-1)$ depth tour, built purely for $O(1)$ LCA via RMQ. They solve different problems and are not interchangeable.

struct LCA {
    int n; vector<int> tin, par, dep; vector<vector<pair<int, int>>> sp;   // sp over preorder: (depth, vertex)
    LCA(const vector<vector<int>>& adj, int root) : n(sz(adj)), tin(n), par(n, -1), dep(n) {
        vector<int> st{root}, order; order.reserve(n);
        while (sz(st)) { int u = st.back(); st.pop_back(); tin[u] = sz(order); order.push_back(u);
            for (int v : adj[u]) if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, st.push_back(v); }
        int K = __lg(n) + 1; sp.assign(K, vector<pair<int, int>>(n));
        for (int i = 0; i < n; i++) sp[0][i] = {dep[order[i]], order[i]};
        for (int k = 1; k < K; k++) for (int i = 0; i + (1 << k) <= n; i++) sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
    }
    int lca(int u, int v) const {
        if (u == v) return u;
        int l = tin[u], r = tin[v]; if (l > r) swap(l, r);
        int k = __lg(r - l);
        return par[min(sp[k][l + 1], sp[k][r - (1 << k) + 1]).second];
    }
    int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
};

Proof: the preorder RMQ formula

Let $a=\text{LCA}(u,v)$ with $\text{tin}(u)<\text{tin}(v)$. If $u=a$, $v$ is in $u$‘s subtree, and the positions $(\text{tin}(u),\text{tin}(v)]$ all lie in $u$‘s subtree below $u$, including the child $c$ of $u$ on the way to $v$ (it is entered before $v$ and after $u$); $c$ has the minimum depth $\text{dep}(u)+1$, and every vertex of depth $\text{dep}(u)+1$ in this range is a child of $u$, so the parent of the minimiser is $u$. If $u\ne a$, then $u$ and $v$ lie in different child subtrees of $a$, the one of $v$ entered after the one of $u$; the range contains the child $c_v$ of $a$ above $v$ (entered between $u$ and $v$) and only vertices strictly inside $a$‘s subtree, so the minimum depth is $\text{dep}(a)+1$ and is attained at children of $a$. Either way the parent of the minimiser is $a$.

Tarjan’s offline LCA

DFS; when a vertex finishes, union it into its parent’s set whose representative points at the parent. A query $(u,v)$ is answered when the second of them is visited: the answer is the current ancestor label of the first one’s set.

vector<int> offlineLCA(const vector<vector<int>>& adj, int root, const vector<pair<int, int>>& qs) {
    int n = sz(adj); DSU d(n); vector<int> anc(n), res(sz(qs)), par(n, -1), it(n); vector<char> vis(n);
    vector<vector<pair<int, int>>> at(n);
    for (int i = 0; i < sz(qs); i++) at[qs[i].first].push_back({qs[i].second, i}), at[qs[i].second].push_back({qs[i].first, i});
    vector<int> st{root}; vis[root] = 1; anc[root] = root;
    while (sz(st)) {
        int u = st.back();
        if (it[u] == 0) for (auto [w, i] : at[u]) if (vis[w]) res[i] = anc[d.find(w)];   // on entering u
        if (it[u] < sz(adj[u])) {
            int v = adj[u][it[u]++];
            if (v == par[u]) continue;
            par[v] = u; vis[v] = 1; anc[v] = v; st.push_back(v);
        } else {
            st.pop_back();
            if (par[u] >= 0) { d.unite(u, par[u]); anc[d.find(u)] = par[u]; }
        }
    }
    return res;
}

Proof: Tarjan's invariant

At any moment let $r_0,\dots ,r_t$ be the DFS stack (root to current). Every visited vertex $w$ belongs to the set of the deepest stack vertex $r_i$ that is an ancestor of $w$, and that set’s label is $r_i$: a finished vertex is merged into its parent, whose label is the parent while the parent is on the stack, and when the parent finishes the merged set moves up again. When we enter $u$ and $w$ was visited earlier, the deepest stack vertex above $w$ is an ancestor of both, and no deeper common ancestor exists (the next stack vertex below it is not an ancestor of $w$). So it is $\text{LCA}(u,w)$. Each query is answered when its later endpoint is entered (the earlier one is then visited; equal endpoints give themselves).

Schieber–Vishkin ($O(n)$ build, $O(1)$ query)

Number vertices in preorder from 1. $I(v)$ is the number in $v$‘s subtree interval with the most trailing zeros; vertices with equal $I$ form vertical paths (“runs”), and $I$ maps the tree onto a complete binary tree in in-order numbering so that ancestors map to ancestors. $A(v)$ has bit $h$ set iff some ancestor of $v$ (or $v$) has $I$ of height $h$. The query finds the height $j$ of the LCA’s run from $I(x),I(y),A(x),A(y)$ with bit operations, then enters that run from both sides.

struct SchieberVishkin {
    int n; vector<int> par, I, dep, head; vector<unsigned> A;
    SchieberVishkin(const vector<vector<int>>& adj, int root) : n(sz(adj)), par(n, -1), I(n), dep(n), head(n + 2), A(n) {
        vector<int> pre(n), sub(n, 1), order, st{root}; order.reserve(n);
        while (sz(st)) { int u = st.back(); st.pop_back(); pre[u] = sz(order) + 1; order.push_back(u);
            for (int v : adj[u]) if (v != par[u]) par[v] = u, dep[v] = dep[u] + 1, st.push_back(v); }
        for (int i = n - 1; i > 0; i--) sub[par[order[i]]] += sub[order[i]];
        for (int u : order) {
            int l = pre[u], r = pre[u] + sub[u] - 1;
            I[u] = r & -(1 << __lg((l - 1) ^ r));              // the most trailing zeros in [l, r]
            A[u] = (par[u] < 0 ? 0u : A[par[u]]) | unsigned(I[u] & -I[u]);
            if (par[u] < 0 || I[par[u]] != I[u]) head[I[u]] = u;  // top of the run
        }
    }
    int enter(int x, int j) const {                         // first vertex of x's root path in the run of height j
        if (__builtin_ctz(A[x]) == j) return x;
        int k = __lg(A[x] & ((1u << j) - 1));
        int Iw = ((I[x] >> (k + 1)) << (k + 1)) | (1 << k);
        return par[head[Iw]];
    }
    int lca(int x, int y) const {
        if (I[x] == I[y]) return dep[x] < dep[y] ? x : y;
        int h = max({__lg(I[x] ^ I[y]), __builtin_ctz(I[x]), __builtin_ctz(I[y])});   // height of LCA of I(x), I(y)
        int j = __builtin_ctz(A[x] & A[y] & (~0u << h));
        int a = enter(x, j), b = enter(y, j);
        return dep[a] < dep[b] ? a : b;
    }
};

Proof: Schieber–Vishkin

Runs. In an interval $[l,r]$ the number with the most trailing zeros is unique ($r$ with the bits below the highest bit where $l-1$ and $r$ differ cleared). If $c$ is a child of $v$, $c$‘s interval lies inside $v$‘s, so $\text{tz}(I(c))\le \text{tz}(I(v))$ with equality iff $I(c)=I(v)$, and at most one child shares $I(v)$. So equal-$I$ vertices form vertical paths (runs), and heights $\text{tz}(I)$ strictly increase from run to run going up; hence $A(v)$ lists the run heights on $v$‘s root path and its lowest bit is $v$‘s own run height.

Embedding. In the complete binary tree $B$ on in-order numbers (node $i$ at height $\text{tz}(i)$), the subtree of a node $z$ of height $t$ is $[z-2^t+1,z+2^t-1]$. With $t=\text{tz}(I(v))$, $v$‘s interval contains no multiple of $2^{t+1}$ (it would have more trailing zeros), so it lies inside the subtree of $I(v)$, and so does $I(c)$ for every descendant $c$. Thus tree ancestors map to $B$-ancestors, and $h$ is the height of the $B$-LCA of $I(x),I(y)$ (the standard formula: the highest differing bit, unless one is an ancestor of the other).

Height of the LCA’s run. Let $z=\text{LCA}(x,y)$. $I(z)$ is a common $B$-ancestor of $I(x),I(y)$, so its height is $\ge h$ and appears in both $A(x),A(y)$. Suppose a common bit $j^{\prime }$ with $h\le j^{\prime }<\text{tz}(I(z))$ exists: $x$ has an ancestor $x^{\prime }$ and $y$ an ancestor $y^{\prime }$ whose runs have height $j^{\prime }$, so $I(x^{\prime })$, $I(y^{\prime })$ are the $B$-ancestors of $I(x)$, $I(y)$ at height $j^{\prime }\ge h$, which coincide. Then $x^{\prime },y^{\prime }$ are on one vertical path, the shallower is a common ancestor of $x$ and $y$, hence an ancestor of $z$, and its height would be $\ge \text{tz}(I(z))>j^{\prime }$: contradiction. So $j$ (the lowest common bit $\ge h$) is the height of $z$‘s run.

Entering. If $x$‘s own run has height $j$, it is $z$‘s run. Otherwise the last run on $x$‘s root path below height $j$ has height $k$ = highest bit of $A(x)$ below $j$, and its $I$-value is the $B$-ancestor of $I(x)$ at height $k$, i.e. $I(x)$‘s bits above $k$, a one, then zeros; the parent of that run’s head is in the next run up, of height $j$. So enter returns the deepest vertex of $x$‘s root path lying in $z$‘s run, and likewise for $y$. Both are descendants of $z$ on one vertical path; the shallower is an ancestor of both $x$ and $y$, hence equals $z$.

Level ancestor in $O(1)$: ladders

Decompose into long paths (each vertex continues into its child of greatest height), extend each path upwards by its own length to get a ladder. To find the $k$-th ancestor, jump $2^{\lfloor \log k\rfloor }$ with binary lifting; the vertex reached has a path below it of length $\ge 2^{\lfloor \log k\rfloor }$, so its ladder covers the remaining $<2^{\lfloor \log k\rfloor }$ steps.

struct LadderAncestor {
    int n, LOG = 1; vector<int> dep, par, pos, ladderOf; vector<vector<int>> up, ladder;
    LadderAncestor(const vector<vector<int>>& adj, int root) : n(sz(adj)), dep(n), par(n, -1), pos(n), ladderOf(n), ladder(n) {
        while ((1 << LOG) < n) LOG++;
        vector<int> order{root}, height(n, 1), heavy(n, -1);
        for (int i = 0; i < sz(order); i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], dep[v] = dep[order[i]] + 1, order.push_back(v);
        for (int i = n - 1; i >= 0; i--) { int u = order[i]; for (int v : adj[u]) if (v != par[u] && height[v] + 1 > height[u]) height[u] = height[v] + 1, heavy[u] = v; }
        up.assign(LOG, vector<int>(n));
        for (int v = 0; v < n; v++) up[0][v] = par[v] < 0 ? v : par[v];
        for (int k = 1; k < LOG; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
        for (int u : order) {
            if (par[u] >= 0 && heavy[par[u]] == u) continue;    // u tops a long path
            vector<int> path, lad;
            for (int v = u; v >= 0; v = heavy[v]) path.push_back(v);
            for (int a = par[u], c = 0; a >= 0 && c < sz(path); a = par[a], c++) lad.push_back(a);
            reverse(all(lad)); int ext = sz(lad);
            lad.insert(lad.end(), all(path));
            for (int i = 0; i < sz(path); i++) pos[path[i]] = ext + i, ladderOf[path[i]] = u;
            ladder[u] = move(lad);
        }
    }
    int kth(int v, int k) const {                           // k-th ancestor, -1 if above the root
        if (k > dep[v]) return -1;
        if (k == 0) return v;
        int h = __lg(k); v = up[h][v]; k -= 1 << h;
        return ladder[ladderOf[v]][pos[v] - k];
    }
};

Proof: ladders answer the remaining jump

After jumping $2^h$ from $v$ to $w$, $w$ has a descendant $2^h$ levels below, so its height (vertices on the longest downward path) is $\ge 2^h+1$, and the long path through $w$ continues downward along maximum heights for at least $2^h$ more vertices. Let that long path have top $t$, length $L$, and let $w$ be at index $i$ from the top; then $L\ge i+2^h+1$. The ladder holds the path plus $\min (L,\text{dep}(t))$ ancestors above $t$. The remaining $k^{\prime }=k-2^h<2^h$ steps either stay on the path ($k^{\prime }\le i$) or need $k^{\prime }-i<2^h<L$ ancestors above $t$, which exist because $k\le \text{dep}(v)$. So the answer is in the ladder at index $\text{pos}(w)-k^{\prime }$. Each ladder has at most twice its path’s length, so all ladders take $\le 2n$ entries.

Path utilities

template <class BL> bool onPath(const BL& t, int a, int b, int x) { return t.dist(a, x) + t.dist(x, b) == t.dist(a, b); }
template <class BL> int kthOnPath(const BL& t, int a, int b, int k) {    // vertex at distance k from a towards b
    int c = t.lca(a, b), da = t.dep[a] - t.dep[c], db = t.dep[b] - t.dep[c];
    return k <= da ? t.jump(a, k) : t.jump(b, da + db - k);
}
template <class BL> tuple<bool, int, int> pathIntersection(const BL& t, int a, int b, int x, int y) {
    array<int, 4> c = {t.lca(a, x), t.lca(a, y), t.lca(b, x), t.lca(b, y)};
    sort(all(c), [&](int p, int q) { return t.dep[p] > t.dep[q]; });
    int u = c[0], v = c[1], l1 = t.lca(a, b), l2 = t.lca(x, y);
    if (u == v && (t.dep[u] < t.dep[l1] || t.dep[u] < t.dep[l2])) return {false, -1, -1};
    return {true, u, v};                                     // the common part is the path u - v
}

Fact	Formula
LCA of a set	LCA of its min-tin and max-tin vertices
meeting point of $u,v,w$ (minimising total distance)	the one of $\text{lca}(u,v),\text{lca}(v,w),\text{lca}(u,w)$ that differs (the deepest)
$x$ on path $a$–$b$	$d(a,x)+d(x,b)=d(a,b)$
additive path updates, queries at the end	$+x$ at $u,v$; $-x$ at the LCA and its parent; subtree sums
intersection of paths $a$–$b$, $x$–$y$	the path between the two deepest of the four cross LCAs, if it lies below both path LCAs

Proof: the path facts

Set LCA: every vertex of the set lies in the preorder interval between the min-tin and max-tin vertices, and the LCA $a$ of those two has a subtree covering that whole interval, so it is a common ancestor; any common ancestor of the set is one of those two, so it is the deepest. Meeting point: among the three pairwise LCAs two coincide (the shallowest) and the third, $m$, is the deepest; $m$ lies on all three pairwise paths, so $d(u,m)+d(v,m)+d(w,m)=\frac{1}{2}(d(u,v)+d(v,w)+d(u,w))$, which is a lower bound for any point by the triangle inequality. Difference trick: a vertex’s final subtree sum gets $+x$ for each of $u,v$ in its subtree, $-x$ if the LCA is in it and $-x$ if the LCA’s parent is; on the path this totals $x$, and $0$ elsewhere. Intersection: a vertex $z$ is on both paths iff it is on the path between the deepest two cross LCAs, by examining where $x$ and $y$ attach to the path $a$–$b$; the special case of equal deepest values is a single vertex, which lies on both paths only if it is below both path LCAs.