Алгоритм Тарьяна поиска LCA за О(1) в оффлайне — различия между версиями

Текущая версия на 22:33, 31 января 2019

Перенаправление на:

@@ Строка 1: / Строка 1: @@
-Алгоритм Тарьяна позволяет находить наименьшего общего предка двух вершин в дереве, если все запросы известны заранее(offline).
+#перенаправление [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
-Каждый запрос к дереву - это 2 вершины v,u для которых нужно найти такую вершину k, что k-предок вершин v и u, и k имеет максимальную глубину из всех таких вершин.
-Алгоритм позволяет найти ответы для дерева из n вершин и m запросов за время О(n + m), т.е при достаточно большом m, за О(1) на запрос.
-== Алгоритм ==
-фывфыв