Lowest Common Ancestor (Binary Lifting)
Lift nodes by powers of two so LCA and ancestor queries become logarithmic after one tree preprocessing pass.
Lowest Common Ancestor (Binary Lifting)
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Lowest common ancestor is the standard query on rooted trees: for two vertices \(u\) and \(v\), find the deepest vertex that is an ancestor of both. Binary lifting is the contest workhorse because it is easy to combine with depth logic and other ancestor-style queries.
When to Use It
Use LCA when:
a problem asks about paths in a rooted tree,
distance, ancestry, or path decomposition repeatedly mentions two vertices,
you need a reusable tree-query baseline before heavier tools like HLD.
Core Idea
Precompute \(\texttt{up[k][v]}\), the \(2^k\)-th ancestor of vertex \(v\). Then:
raise the deeper node until both nodes are at the same depth,
lift both nodes together from large powers to small until their ancestors diverge,
the parent just above that divergence is the LCA.
Key Insight
Binary lifting turns ancestor climbing into bit decomposition. Moving up \(13\) levels is the same as moving up \(8 + 4 + 1\) levels. That is exactly what the jump table stores.
Operations / Main Technique
DFS or BFS to compute parent and depth,
build the jump table,
answer
lca(u, v),support
kth_ancestor(v, k)and distance queries as well.
Worked example.
If one node is 11 levels deeper than the other, binary lifting raises it by the set bits of \(11\), namely \(8 + 2 + 1\), before the paired lifting phase starts.
Correctness Intuition
The first phase preserves the LCA because only the deeper node moves upward. In the second phase, if the \(2^k\)-ancestors of the two nodes differ, both nodes can safely jump there without passing the LCA. After all such jumps, they sit directly below the LCA.
Complexity Analysis
preprocessing: \(O(n \log n)\),
one LCA query: \(O(\log n)\),
memory: \(O(n \log n)\).
Implementation
The code builds the binary-lifting table from a rooted tree and supports:
kth_ancestor,lca,distance.
Common Pitfalls
Forgetting to root the tree consistently.
Using too few lifting levels for the maximum \(n\).
Mixing edge count and vertex depth conventions in distance formulas.
Recursion depth issues on deep trees if DFS is used directly.
Variants / Extensions
Euler tour plus RMQ for \(O(1)\) LCA queries after different preprocessing.
Binary lifting for functional graphs.
Path queries combined with HLD or Euler-tour flattening.
Practice Problems
Distance queries on a tree.
K-th ancestor or jump queries.
Path intersection or meeting-point problems on trees.
References
Code
Contest-ready reference implementation for the idea explained above.
struct LcaBinaryLifting {
int n;
int logn;
vector<int> depth;
vector<vector<int>> up;
LcaBinaryLifting(const vector<vector<int>>& tree, int root = 0) {
n = (int)tree.size();
logn = 1;
while ((1 << logn) <= n) {
++logn;
}
depth.assign(n, 0);
up.assign(logn, vector<int>(n, root));
queue<int> q;
vector<int> parent(n, root);
vector<int> seen(n, 0);
seen[root] = 1;
q.push(root);
while (!q.empty()) {
int v = q.front();
q.pop();
up[0][v] = parent[v];
for (int to : tree[v]) {
if (seen[to]) continue;
seen[to] = 1;
parent[to] = v;
depth[to] = depth[v] + 1;
q.push(to);
}
}
for (int k = 1; k < logn; ++k) {
for (int v = 0; v < n; ++v) {
up[k][v] = up[k - 1][up[k - 1][v]];
}
}
}
int kth_ancestor(int v, int k) const {
for (int bit = 0; bit < logn; ++bit) {
if (k & (1 << bit)) {
v = up[bit][v];
}
}
return v;
}
int lca(int a, int b) const {
if (depth[a] < depth[b]) {
swap(a, b);
}
a = kth_ancestor(a, depth[a] - depth[b]);
if (a == b) {
return a;
}
for (int k = logn - 1; k >= 0; --k) {
if (up[k][a] != up[k][b]) {
a = up[k][a];
b = up[k][b];
}
}
return up[0][a];
}
int distance(int a, int b) const {
int c = lca(a, b);
return depth[a] + depth[b] - 2 * depth[c];
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.