Изменения
Нет описания правки
запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] ,
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex>O(n \log n),
O(\log n)</tex> >. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам ассимптотику асимптотику < <tex>O(n^2), O(1)</tex> >.
В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ <tex>h</tex>.
Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас <tex>O(n)</tex> времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику асимптотику до <tex>O(n \log n)</tex>.
=== Двоичные подъемы ===
После этого посчитаем двоичные подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотикуасимптотику.
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log n</tex>
*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем <tex>S(n)</tex>.
*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за < <tex>O(\dfrac{n}{S(n)} \log n + n), O(1)</tex> >. Получаем алгоритм < <tex>O(n), O(1) </tex> >. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает ассимптотику асимптотику предподсчета <tex>O(\sqrt{n} \log^2{n}) = o(n) = O(n)</tex>.
В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> >.
