Наименьший общий предок
Пусть дано дерево с корнем.
Наименьший общий предок двух вершин и — это самая глубокая вершина, которая является предком и для , и для .
Проще говоря: если идти от и вверх к корню, то LCA — это первая вершина, где их пути пересекаются.
Мы предполагаем, что:
Если является предком , то ответ — это .
Иначе будем поднимать вверх.
Идея:
мы хотим поднять как можно выше, но при этом не зайти в вершину, которая уже является предком .
Для этого пробуем прыжки большой длины (как в бинарном подъёме):
В итоге мы окажемся в вершине , которая уже почти LCA, но сама ещё не является предком .
Тогда её родитель и будет ответом.
Этот способ обычно считается более понятным и чаще используется на практике.
Теперь обе вершины находятся на одной глубине.
Если после выравнивания глубин оказалось, что , то это и есть LCA — возвращаем .
Если , значит LCA находится выше.
Будем поднимать обе вершины одновременно, начиная с самых больших прыжков:
Идём от больших прыжков к меньшим.
В конце и окажутся прямо под LCA. Ответ — это их непосредственный родитель:
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);
}
// поднимаем y до глубины 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];
}