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>О(1)</tex> на запрос.
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим обход в глубину из её.
