74
правки
Изменения
Нет описания правки
Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее(offline).
Каждый запрос к дереву - это 2 вершины <tex>v</tex>,<tex>u</tex> для которых нужно найти такую вершину <tex>k</tex>, что <tex>k</tex>-предок вершин <tex>v</tex> и <tex>u</tex>, и <tex>k</tex> имеет максимальную глубину из всех таких вершин.
Алгоритм позволяет найти ответы для дерева из n вершин и m запросов за время <tex>О(n + m)</tex>, т.е при достаточно большом m, за <tex>О(1)</tex> на запрос.
== Алгоритм ==
Запустим обход в глубину из корня в течении которого мы найдём все ответы на наши запросы.Ответ для вершин v,u находится, когда мы уже посетели вершины u, а в v обработали всех сыновей и собираемся выйти из неё.
Зафиксируем момент, мы собираемся выйти из вершины v(обработали всех сыновей) и хотим узнать ответ для пары v,u.Тогда заметим что ответ - это либо вершина v, либо какой-то её предок.Значит нам нужно найти предок вершины v, который является предком вершины u с наибольшей глубиной. Заметим, что при фиксированном v каждый из предков вершины v порождает некоторый класс вершин u, для которых он является ответом(в этом классе содержатся все вершины которые находятся "слева" от этого предка).
На рисунке разные цвета-разные классы,а белые вершины ещё не просмотренные в dfs.
Классы этих вершин - не пересекаются,а значит мы их можем эффективно обрабаывать с помощью dsu.
Будем поддерживать массив ancestor[v] - представитель множества в котором содержится вершина v.
Для каждого класса мы образуем множество, и представителя этого множества.
Когда мы приходим в новую вершину v мы должны добавить её в новый класс(ancestor[v] = v),а когда просмотрим всё поддерево какого-то ребёнка, мы должны объеденить это поддерево с нашим классом(операция union), и не забыть установить представителя как вершину v(взависимости от реализации это может быть какая-то другая вершина).
После того как мы обработали всех детей вершины v,мы можем ответить на все запросы вида (v,u) где u-уже посещённая вершина.
Нетрудно заметить что ответ для lca(v,u) = ancestor(find(u)).Так же можно понять что для каждого запроса это условие(что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
=== Оценка сложности ===
Она состоит из нескольких оценок.
Во-первых dfs работает О(n).Во-вторых, операции по объединению множеств, которые в сумме для всех разумных n затрачивают <tex>О(n)</tex> операций. В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных n выполняется за <tex>О(1)</tex>. Итоговая асимптотика получается <tex>\mathrm{O(n + m)}</tex>, но при достаточно больших m ответ за <tex>О(1)</tex> на один запрос.
