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