Алгоритм Тарьяна поиска LCA за О(1) в оффлайне
Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее (offline). Каждый запрос к дереву — это </tex>2</tex> вершины , для которых нужно найти такую вершину , что -предок вершин и , и имеет максимальную глубину из всех таких вершин. Алгоритм позволяет найти ответы для дерева из n вершин и m запросов за время , т.е при достаточно большом m, за на запрос.
Алгоритм
Подвесим наше дерево за любую вершину, и запустим обход в глубину из её. Ответ на каждый запрос мы найдём в течение поиска в глубину. Ответ для вершин , находится, когда мы уже посетили вершину , а так же посетили всех сыновей вершины , и собираемся выйти из неё.
Зафиксируем момент: мы собираемся выйти из вершины (обработали всех сыновей) и хотим узнать ответ для пары , .F Тогда заметим, что ответ — это либо вершина , либо какой-то её предок. Значит, нам нужно найти предка вершины , который является предком вершины с наибольшей глубиной. Заметим, что при фиксированном каждый из предков вершины порождает некоторый класс вершин , для которых он является ответом, в этом классе содержатся все вершины которые находятся "слева" от этого предка.
На рисунке разные цвета — разные классы,а белые вершины ещё не просмотренные в .
Классы этих вершин не пересекаются, а значит мы их можем эффективно обрабатывать с помощью dsu.
Будем поддерживать массив — представитель множества в котором содержится вершина . Для каждого класса мы образуем множество, и представителя этого множества. Когда мы приходим в новую вершину мы должны добавить её в новый класс (), а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция ), и не забыть установить представителя как вершину (в зависимости от реализации это может быть какая-то другая вершина).
После того как мы обработали всех детей вершины , мы можем ответить на все запросы вида (,) где — уже посещённая вершина. Нетрудно заметить что ответ для .Так же можно понять что для каждого запроса это условие (что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
Предположим, что нашли предка, который не является наименьшим, тогда это нас моментально приводит к противоречию, потому что запросмы должны были рассмотреть ранее — на минимальном предке. Если он не минимальный, значит, есть на какой-то большей глубине, то есть такая вершина, которая была посещена раньше и для которой условия на и .
Реализация
bool visited[n];
vector <int> query[n];
int dsu_get (int v)
return v == dsu[v] ? v : dsu[v] = dsu_get (dsu[v]);
unite (int a, int b, int new_ancestor)
a = dsu_get (a);
b = dsu_get (b);
dsu[a] = b;
ancestor[b] = new_ancestor;
dfs(int v)
visited[v] = true;
for (u таких, что (v, u) — ребро в G)
if (not visited[u])
dfs(u);
union(v, u, v);
for (i = 0; i < query[v].size; i++)
if (visited[query[v][i]])
cout << "LCA " << v << " " << u << " = " << ancestor[dsu_get(q[v][i])];
int main()
dfs(1); // можно запускать от любой вершины
Оценка сложности
Она состоит из нескольких оценок.
Во-первых, обход в глубину работает .
Во-вторых, операции по объединению множеств, которые в сумме для всех разумных затрачивают операций.
Каждый запрос будет рассмотрен дважды — при посещение вершины и , но обработан лишь один раз, поэтому можно считать, что все запросы обработаются суммарно за .
В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных выполняется за . Итоговая асимптотика получается , но при достаточно больших ответ за на один запрос.
