Изменения
Нет описания правки
Дано дерево и набор запросов: пары вершин <tex>\langle v, u \rangle </tex>, и для каждой пары нужно найти наименьшего общего предка. Запросы нам Считаем, что все запросы известны заранее, т.е задача сформулирована в режиме поэтому будем решать задачу оффлайн.Алгоритм позволяет найти ответы для дерева из <tex>n</tex> вершин и <tex>m</tex> запросов за время <tex>O (n + m)</tex>, т.е то есть при достаточно большом <tex>m</tex>, за <tex>O (1)</tex> на запрос.
== Алгоритм ==
Подвесим наше дерево за любую вершину, и запустим [[Обход в глубину, цвета вершин|обход в глубину]] из её.
В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных <tex>n</tex> выполняется за <tex>O (1)</tex>. Итоговая асимптотика получается <tex>O (n + m)</tex>, но при достаточно больших <tex>m</tex> ответ за <tex>O (1)</tex> на один запрос.
== Источники информации ==* [http://e-maxx.ru/algo/lca_linear_offline e-maxxMAXimal :: algo :: Наименьший общий предок.ru - алгоритмыНахождение за O(1) в оффлайн (алгоритм Тарьяна) ]* [http://habrahabr.ru/post/104772 habrahabr Habrahabr {{--- }} Система непересекающихся множеств и её применения] [[Категория: Дискретная математика и алгоритмы]][[Категория: Задача о наименьшем общем предке]]
