286
правок
Изменения
Нет описания правки
Дано [[Дерево, эквивалентные определения | дерево ]] <tex> G </tex> и набор запросов: пары вершин <tex>\langle v, u \rangle </tex>. Для каждой пары нужно найти наименьшего общего предка. Считаем, что все запросы известны заранее, поэтому будем решать задачу оффлайн.
Алгоритм позволяет найти ответы для дерева из <tex>n</tex> вершин и <tex>m</tex> запросов за время <tex>O (n + m)</tex>, то есть при достаточно большом <tex>m</tex> за <tex>O (1)</tex> на запрос.
== Алгоритм ==
dfs(u)
union(v, u, v)
'''foreachfor''' (u : <tex>\langle v, u \rangle </tex> {{---}} есть такой запрос)
'''if''' visited[u]
запомнить, что ответ для запроса <tex>\langle v, u \rangle </tex> = lcaClass[find[u]]
Следовательно, итоговая асимптотика {{---}} <tex>O (n + m)</tex>, что при достаточно больших <tex>m</tex> составляет <tex>O (1)</tex> на один запрос.
==См. также==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Heavy-light декомпозиция]]
== Источники информации ==
