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>O (n + m)</tex>, т.е при достаточно большом m, за <tex>O (1)</tex> на запрос.
== Алгоритм ==
Зафиксируем момент, мы собираемся выйти из вершины <tex>v</tex> (обработали всех сыновей) и хотим узнать ответ для пары <tex>v</tex>, <tex>u</tex>.
Тогда заметим что ответ {{---}}, это либо вершина <tex>v</tex>, либо какой-то её предок. Значит нам нужно найти предок вершины <tex>v</tex>, который является предком вершины <tex>u</tex> с наибольшей глубиной. Заметим, что при фиксированном <tex>v</tex> каждый из предков вершины <tex>v</tex> порождает некоторый класс вершин <tex>u</tex>, для которых он является ответом (в этом классе содержатся все вершины которые находятся "слева" от этого предка).
На рисунке разные цвета{{---}} разные классы,а белые вершины ещё не просмотренные в <tex>dfs</tex>.
Классы этих вершин {{- --}} не пересекаются, а значит мы их можем эффективно обрабатывать с помощью <tex>dsu</tex>.Будем поддерживать массив <tex>ancestor[v]</tex> {{--- }} представитель множества в котором содержится вершина <tex>v</tex>.
Для каждого класса мы образуем множество, и представителя этого множества.
Когда мы приходим в новую вершину <tex>v</tex> мы должны добавить её в новый класс (<tex>ancestor[v] = v</tex>), а когда просмотрим всё поддерево какого-то ребёнка, мы должны объединить это поддерево с нашим классом (операция <tex>union</tex>), и не забыть установить представителя как вершину <tex>v</tex> (в зависимости от реализации это может быть какая-то другая вершина).
К самой первой вершине этого пути, до которой мы доберёмся, если будем просто подниматься. Очевидно, это и есть <tex>lca</tex>.
После того как мы обработали всех детей вершины <tex>v</tex>, мы можем ответить на все запросы вида (<tex>v</tex>,<tex>u</tex>) где <tex>u</tex>{{---}} уже посещённая вершина.
Нетрудно заметить что ответ для <tex>lca(v, u) = ancestor(find(u))</tex>.Так же можно понять что для каждого запроса это условие(что одна вершина уже посещена, а другую мы обрабатываем) выполнится только один раз.
[[file:mytree.png|500px|разные цвета{{---}} разные классы, а белые вершины ещё не просмотренные в dfs]]
=== Реализация ===
