Алгоритм Тарьяна поиска LCA за О(1) в оффлайне
Дано дерево и набор запросов: пары вершин , и для каждой пары нужно найти наименьшего общего предка. Запросы нам известны заранее, т.е задача сформулирована в режиме оффлайн. Алгоритм позволяет найти ответы для дерева из вершин и запросов за время , т.е при достаточно большом , за на запрос.
Содержание
Алгоритм
Подвесим наше дерево за любую вершину, и запустим обход в глубину из её. Ответ на каждый запрос мы найдём в течение поиска в глубину. Ответ для вершин находится, когда мы уже посетили вершину , а так же посетили всех сыновей вершины , и собираемся выйти из неё.
Зафиксируем момент: мы собираемся выйти из вершины (обработали всех сыновей) и хотим узнать ответ для пары , . Тогда заметим, что ответ — это либо вершина , либо какой-то её предок. Значит, нам нужно найти предка вершины , который является предком вершины с наибольшей глубиной. Заметим, что при фиксированном каждый из предков вершины порождает некоторый класс вершин , для которых он является ответом, в этом классе содержатся все вершины которые находятся "слева" от этого предка.
На рисунке разные цвета — разные классы,а белые вершины ещё не просмотренные в .
Классы этих вершин не пересекаются, а значит мы их можем эффективно обрабатывать с помощью системы непересекающихся множеств, которую будем храниться в массиве .
Будем поддерживать массив — представитель множества в котором содержится вершина . Для каждого класса мы образуем множество, и представителя этого множества. Когда мы приходим в новую вершину мы должны добавить её в новый класс (), а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция ), и не забыть установить представителя как вершину (в зависимости от реализации это может быть какая-то другая вершина).
После того как мы обработали всех детей вершины , мы можем ответить на все запросы вида где — уже посещённая вершина. Нетрудно заметить что ответ для = ancestor[find(u)]</tex>.Так же можно понять что для каждого запроса это условие (что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
Предположим, что нашли предка, который не является наименьшим, тогда это нас моментально приводит к противоречию, потому что запросмы должны были рассмотреть ранее — на минимальном предке. Если он не минимальный, значит, есть на какой-то большей глубине, то есть такая вершина, которая была посещена раньше и для которой условия на и выполнялись, значит, тогда должна была найтись эта вершина в качестве .
Реализация
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 : (v, u) 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]]
запомнить, что ответ для запроса (v,u) = ancestor[dsu_get(q[v][i])]
Оценка сложности
Она состоит из нескольких оценок.
Во-первых, обход в глубину работает .
Во-вторых, операции по объединению множеств, которые в сумме для всех разумных затрачивают операций.
Каждый запрос будет рассмотрен дважды — при посещение вершины и , но обработан лишь один раз, поэтому можно считать, что все запросы обработаются суммарно за .
В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных выполняется за . Итоговая асимптотика получается , но при достаточно больших ответ за на один запрос.
