LCA - lowest (least) common ancestor
Наименьший общий предок двух вершин
Для начала давайте разберемся, что такое общий предок двух вершин \(u\) и \(v\).
Это любая такая вершина \(t\), которая лежит на пути от корня до \(u\) и на пути от корня до \(v\).
Тогда наименьшим общим предком \(u\) и \(v\) назовем такую вершину \(t\), которая является их общим предком, и расстояние от корня до нее максимально.
Зачем нужно уметь его искать?
В последнее время я все реже встречаю задачи, требующие именно явного нахождения наименьшего общего предка, но порой попадаются задачи про запросы на пути, а с ними нам может помочь LCA.
Наивная реализация
Для начала рассмотрим самую простую реализацию поиска LCA:
vector<vector<int>> gr; \\ наш граф
vector<int> pre; \\ массив предков
vector<int> d; \\ массив глубин
void dfs(int v, int p = -1) {
if (p == -1)
d[v] = 0;
else
d[v] = d[p] + 1;
pre[v] = p;
for (int to : gr[v])
if (to != p)
dfs(to, v);
}
int getLCA(int a, int b) {
while (a != b) {
if (d[a] > d[b])
a = pre[a];
else
b = pre[b];
}
return a;
}
int main() {
... // считываем граф
dfs(root) // запускаем дфс от корня
for () {
... // считываем запрос
getLCA(a, b); // отвечаем на него
}
}
Почему это верно?
Давайте посмотрим, что делает наш алгоритм. Пусть сейчас выбраны вершины \(a\) и \(b\).
Их LCA имеет глубину не больше, чем минимум из глубин \(a\) и \(b\), так как лежит на пути от корня до этих вершин.
Значит, если глубины вершин неравны, то можно смело заменять более глубокую вершину ее предком.
Теперь допустим, что глубины вершин одинаковы.
Тогда если они равны, то очевидно что это и есть LCA.
Иначе, LCA имеет губину меньшую, чем та, на которой сейчас расположены вершины, и опять можно заменить их своими предками.
Отлично, теперь давайте оценим время работы.
dfs() отработает за O(n)
getLCA() в худшем случае будет работать за O(n) (например, если граф - бамбук, и мы спрашиваем ответ от его концов)
Таким образом, алгоритм работает за O(q * n) - достаточно долго.
Здесь и далее \(n\) - число вершин в графе, а \(q\) - количество запросов
Давайте попробуем ускорить наш алгоритм.
Метод двоичных подъёмов
Если очень внимательно посмотреть на предыдущую реализацию, то можно заметить два этапа в ней:
Первый - глубина вершин выравнивается.
Второй - вершины параллельно поднимаются наверх, пока не станут равными.
Тогда давайте ходить не по 1, а большими блоками. Например, степенями двойки.
Для начала разберемся, как их предпосчитать.
vector<vector<int>> gr;
vector<int> d;
vector<vector<int>> bl; // бинарные подъемы
// этот массив следует инициализировать так: bl[log(n)+1][n]
// log(n)+1 ассив по n элементов
void dfs(int v, int p = -1) {
if (p == -1) {
p = v;
d[v] = 0;
}
else
d[v] = d[p] + 1;
bl[0][v] = p;
for (int i = 1; i < bl.size(); ++i)
bl[i][v] = bl[i-1][bl[i-1][v]];
for (int to : gr[v])
dfs(to, v);
}
Почему это работает? В цикле построения bl мы говорим, что подняться на \(2^i\) то же самое, что подняться на \(2^{i-1}\) два раза.
Как можно заметить, в такой реализации нельзя подняться выше корня, а значит, не нужны дополнительные if.
Как же тут отвечать на запрос? Давайте разбираться.
int getLCA(int a, int b) {
if (d[a] > d[b])
swap(a, b);
// Теперь b глубже a
for (int i = bl.size() - 1; i >= 0; --i)
if (d[bl[i][b]] >= d[a])
b = bl[i][b];
// Теперь их глубины равны
if (a == b)
return a; // Если они равны, то это и есть LCA
for (int i = bl.size() - 1; i >= 0; --i)
if (bl[i][b] != bl[i][a]) {
a = bl[i][a];
b = bl[i][b];
}
//Теперь верно, что a != b и их глубина минимальна
return bl[0][a];
}
Теперь есть два варианта:
Первый - вы верите мне, что это работает. Тогда делайте *ТЫК* и читайте дальше
Второй - вы хотите понять, что вообще произошло. Тогда продолжайте читать дальше.
Для начала докажем, что работает первый этап и глубина b становится равной глубине a.
Рассмотрим число \(x = (d[b] - d[a])\),
тогда когда мы пойдем от меньшего бита к большему, мы будем совершать переход только тогда, когда этот бит есть в числе.
Почему? Потому что если степень двойки больше, чем максимальный бит числа, то эта степень точно больше самого числа.
Значит, мы будем всегда совершать переход по самому большому биту числа.
После этого расстояние уменьшится на эту степень двойки, и мы перейдем к меньшему расстоянию, с которым по аналогии возьмем переход в соответствии с максимальным битом.
Кстати, на этом можно основать некоторую оптимизацию. Вместо цикла
for (int i = bl.size() - 1; i >= 0; --i)
if (d[bl[i][b]] >= d[a])
b = bl[i][b];
int x = d[b] - d[a];
for (int i = bl.size() - 1; i >= 0; --i)
if (x & (1 << i))
b = bl[i][b];
А что происходит на втором этапе?
Вообще, мы хотим максимально подняться так, чтобы a было все еще не было равно b.
Значит, есть какая-то глубина x, на которую нам хотелось бы подняться, но мы ее не знаем. У нас есть условие \(a \neq b\), которое мы и будем использовать.
Опять таки, мы не можем перейти по биту больше, чем максимальный, а по максимальному можем всегда. Так мы поднимемся максимально и сохраним \(a\neq b\), а значит, их предок уже таков, что \(pre[a] = pre[b]\), следовательно, это и есть LCA.
Что еще умеют бинподъемы?
Например, можно посчитать какую-то функцию на пути, параллельно с поиском LCA.
Для этого давайте хранить bl как массив пар вида \( [to, f] \) - куда нужно перейти, и какое значение функции на этом переходе.
Покажу на примере минимума. Он хорош тем, что нельзя брать его на пути до корня, а потом вычитать ответ на пути от LCA до корня.
Например, сумму можно считать так: если \(sum[v]\) - сумма на пути до вершины v, то сумма на пути от a до b считается как \(sum[a] + sum[b] - 2 * sum[LCA]\). Это если значения записаны на ребрах.
С минимумом так не выйдет.
vector<vector<pair<int, int>>> gr;
vector<int> d;
vector<vector<pair<int, int>>> bl;
void dfs(int v, int p = -1, int pEdge = inf) {
if (p == -1) {
p = v;
d[v] = 0;
}
else
d[v] = d[p] + 1;
bl[0][v] = {p, pEdge};
for (int i = 1; i < bl.size(); ++i)
bl[i][v] = {bl[i-1][bl[i-1][v].first].first, min(bl[i-1][v].second, bl[i-1][bl[i-1][v].first].second);
for (pair<int, int> to : gr[v])
dfs(to.first, v, to.second);
}
int getMIN(int a, int b) {
int ans = inf;
if (d[a] > d[b])
swap(a, b);
for (int i = bl.size() - 1; i >= 0; --i)
if (d[bl[i][b].first] >= d[a]) {
ans = min(ans, bl[i][b].second);
b = bl[i][b].first;
}
if (a == b)
return ans;
for (int i = bl.size() - 1; i >= 0; --i)
if (bl[i][b].first != bl[i][a].first) {
ans = min(ans, bl[i][b].second);
ans = min(ans, bl[i][a].second);
a = bl[i][a].first;
b = bl[i][b].first;
}
ans = min({ans, bl[i][b].second, bl[i][a].second});
return ans;
}
Ну и самое важное: время и память!
Как можно заметить, алгоритм требует \(O(n \cdot log(n))\) памяти и \(O(n \cdot log(n))\) времени на предподсчет
Но вот ответ на запрос занимает всего \(O(log(n))\)
Получаем \(O(n \cdot log(n) + q \cdot log(n))\)
А как еще можно?
Можно свести LCA к RMQ и решать его любыми удобными вам методами - ДО, Sparse-table.
Как свести? Давайте выпишем Эйлеров обход графа. Тогда ответом будет вершина на полуинтервале \([min(first[a], first[b]), max(last[a], last[b]))\), глубина которой минимальна.
Здесть first и last - массивы первых и последних вхождений вершины в Эйлеров обход.
vector<vector<int>> gr;
vector<int> d;
vector<pair<int, int>> euler;
vector<int> first;
vector<int> last;
void dfs(int v, int p = -1) {
if (p == -1)
d[v] = 0;
else
d[v] = d[p] + 1;
first[v] = euler.size();
euler.push_back({v, d[v]});
for (int to : gr[v]) {
dfs(to, v);
euler.push_back({v, d[v]});
}
last[v] = euler.size();
}
Теперь можно взять первый элемент и минимум по вторым элементам пар на полуинтервале, это и будет LCA.
Почему так? Эйлеров обход записывает вершину в самом начале и после обхода каждого поддерева. То есть, если минимум на отрезке - какая-то вершина v, то две данные находятся в разных ее поддеревьях.
Какие плюсы и минусы?
К плюсам можно отнести то, что используя столько же памяти, сколько бинарные подъемы, можно построить sparse-table и отвечать на запросы за O(1).
А также, что можно использовать O(n) памяти, например - ДО.
Минусы - нельзя вычислять что-то на пути (только если это не Мо... Но это лучше даже в голову не брать.)
А ещё?
Есть алгоритм, требующий \(O(n)\) как памяти, так и времени на предподсчет. Отвечает на запрос он за \(O(1)\).
Но рассказывать его я не буду (пока уж точно), так как он мало применим на практике и будет бесполезен на олимпиадах.
ВАЖНО!
Все алгоритмы, описанные в данном тексте, умеют отвечать на запросы онлайн. Запрос пришел - мы ответили.
Бинарные подъемы умеют даже добавлять вершину в дерево. Для этого нужно просто представить, что мы пришли в нее в ходе дфс, и пройтись циклом по степеням двойки.
Если все запросы известны заранее, лучше использовать алгоритм Тарьяна. Про него я напишу отдельно.
Ну и на последок, задачки: Тренировка СПБГУ про LCA