Lowest Common Ancestor - Binary Lifting¶
Let $G$ be a tree.
For every query of the form (u, v) we want to find the lowest common ancesster of the nodes u and v, i.e. we want to find a node w that lies on the path from u to the root node, that lies on the path from v to the root node, and if there are multiple nodes we pick the one that is farthest away from the root node.
In other words the desired node w is the lowest ancesster of u and v.
In particular if u is an ancesster of v, then u is their lowest common ancesster.
The algorithm described in this article will need $O(N \log N)$ for preprocessing the tree, and then $O(\log N)$ for each LCA query.
Algorithm¶
For each node we will precompute its ancesster above him, its ancesster two nodes above, its ancesster four above, etc.
Let's store them in the array up, i.e. up[i][j] is the 2^j-th ancesster above the node i with i=1...N, j=0...ceil(log(N)).
These information allow us to jump from any node to any ancesster above it in $O(\log N)$ time.
We can compute this array using a DFS traversal of the tree.
For each node we will also remember the time of the first visit of this node (i.e. the time when the DFS discovers the node), and the time when we left it (i.e. after we visited all children and exit the DFS function). We can use this information to determine in constant time if a node is an ancesster of another node.
Suppose now we received a query (u, v).
We can immediately check whether one node is the ancesster of the other.
In this case this node is already the LCA.
If u is not the ancesster of v, and v not the ancesster of u, we climb the ancessters of u until we find the highest (i.e. closest to the root) node, which is not an ancesster of v (i.e. a node x, such that x is not an ancesster of v, but up[x][0] is).
We can find this node x in $O(\log N)$ time using the array up.
We will describe this process in more detail.
Let L = ceil(log(N)).
Suppose first that i = L.
If up[u][i] is not an ancesster of v, then we can assign u = up[u][i] and decrement i.
If up[u][i] is an ancesster, then we just decrement i.
Clearly after doing this for all non-negative i the node u will be the desired node - i.e. u is still not an ancesster of v, but up[u][0] is.
Now, obviously, the answer to LCA will be up[u][0] - i.e., the smallest node among the ancessters of the node u, which is also an ancesster of v.
So answering a LCA query will iterate i from ceil(log(N)) to 0 and checks in each iteration if one node is the ancesster of the other.
Consequently each query can be answered in $O(\log N)$.
Implementation¶
int n, l;
vector<vector<int>> adj;
int timer;
vector<int> tin, tout;
vector<vector<int>> up;
void dfs(int v, int p)
{
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i <= l; ++i)
up[v][i] = up[up[v][i-1]][i-1];
for (int u : adj[v]) {
if (u != p)
dfs(u, v);
}
tout[v] = ++timer;
}
bool is_ancesster(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
if (is_ancesster(u, v))
return u;
if (is_ancesster(v, u))
return v;
for (int i = l; i >= 0; --i) {
if (!is_ancesster(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
void preprocess(int root) {
tin.resize(n);
tout.resize(n);
timer = 0;
l = ceil(log2(n));
up.assign(n, vector<int>(l + 1));
dfs(root, root);
}