Lowest common ancestor (binary lifting)
The -th ancestor of every vertex in a table. With it, -th ancestor, LCA and tree distance, each in .
When
Queries on a tree: "who is the -th boss of ?", "who is the common boss of and ?", "how many edges apart are and ?".
The idea
is the parent of , and : two jumps of make one of . The root is its own ancestor, so jumps that would leave the tree stop there.
- -th ancestor: write in binary and make one jump for each set bit.
- LCA: first bring and to the same depth. If they coincide, you are done. Otherwise, from the largest down, jump with both together while their ancestors differ. At the end they are children of the LCA.
- Distance: .
Depths and parents come from a BFS, not a recursive DFS. In Company Queries the tree can be a chain of length .
Pitfalls
- The "while they differ" move is the whole point. If you jump while they are equal, you overshoot the LCA and end at the root.
- In
Company Queries Ithe -th boss may not exist (answer ). Check before jumping, because the code here silently stops at the root.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Lowest common ancestor with binary lifting. Build O(n log n), query O(log n).
// up[k][v] = the 2^k-th ancestor of v (the root is its own ancestor).
// The tree is given as an adjacency list; depths come from an iterative BFS.
struct LCA {
int n;
int LOG;
vector<vector<int>> up;
vector<int> depth;
LCA(const vector<vector<int>>& adj, int root) : n(adj.size()), depth(adj.size(), -1) {
LOG = 1;
while ((1 << LOG) < n) {
LOG++;
}
up.assign(LOG + 1, vector<int>(n, root));
queue<int> q;
depth[root] = 0;
q.push(root);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (depth[v] == -1) {
depth[v] = depth[u] + 1;
up[0][v] = u;
q.push(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]];
}
}
}
int kthAncestor(int v, int k) {
for (int j = 0; j <= LOG; j++) {
if ((k >> j) & 1) {
v = up[j][v];
}
}
return v;
}
int lca(int a, int b) {
if (depth[a] < depth[b]) {
swap(a, b);
}
a = kthAncestor(a, depth[a] - depth[b]);
if (a == b) {
return a;
}
for (int k = LOG; 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) {
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
};
Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Company Queries I · Tree Algorithms
- Company Queries II · Tree Algorithms
- Distance Queries · Tree Algorithms
More in the USACO Guide
- Binary Jumping · usaco.guide/plat/binary-jump
In English, with more problems per level.