3622
правки
Изменения
Нет описания правки
Дано дерево и набор запросов: пары вершин <tex>\langle v, u \rangle </tex>, и для каждой пары нужно найти наименьшего общего предка. Считаем, что все запросы известны заранее, поэтому будем решать задачу оффлайн.
Алгоритм позволяет найти ответы для дерева из <tex>n</tex> вершин и <tex>m</tex> запросов за время <tex>O (n + m)</tex>, то есть при достаточно большом <tex>m</tex>, за <tex>O (1)</tex> на запрос.
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим [[Обход в глубину, цвета вершин|обход в глубину]] из неё.
