Изменения

Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее (offline).

Каждый запрос к дереву {{---}} это </tex>2</tex> вершины <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>dfs'a</tex>. Ответ для вершин <tex>v</tex>, <tex>u</tex> находится, когда мы уже посетили вершины <tex>u</tex>, а в <tex>v</tex> обработали всех сыновей и собираемся выйти из неё.