Lowest common ancestor
Let a rooted tree be given.
The lowest common ancestor of two vertices and is the deepest vertex that is an ancestor of both and .
Simply put: if you go from and up to the root, then the LCA is the first vertex where their paths intersect.
We assume that:
If is an ancestor of , then the answer is .
Otherwise, we will lift upward.
Idea:
we want to lift as high as possible, but at the same time not enter a vertex that is already an ancestor of .
To do this, we try large-length jumps (as in binary lifting):
As a result, we will end up at a vertex that is almost the LCA, but itself is not yet an ancestor of .
Then its parent will be the answer.
This method is usually considered more understandable and is used more often in practice.
Now both vertices are at the same depth.
If after equalizing depths it turns out that , then this is the LCA — return .
If , then the LCA is higher.
We will lift both vertices simultaneously, starting with the largest jumps:
We go from larger jumps to smaller ones.
At the end, and will be directly under the LCA. The answer is their immediate parent:
int lca(int x, int y) {
if (isParent(x, y)) {
return x;
}
for (int i = L; i >= 0; i--) {
if (!isParent(par[x][i], y)) {
x = par[x][i];
}
}
return par[x][0];
}
int lca(int x, int y) {
if (dip[x] > dip[y]) {
swap(x, y);
}
// lift y to the depth of x
y = jump(y, dip[y] - dip[x]);
if (x == y) {
return x;
}
for (int i = L; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}