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