Изменения
Нет описания правки
{{Задача
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация и двоичные подъемы ==
[[Файл:LevelAncestor.png|200px|thumb|right]]
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>, что так же в худшем случае работает за <tex>O(n)</tex>. Получили алгоритм за < <tex>O(n), O(n)</tex> >, где время ответа на запрос можно улучшить до <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>, на который алгоритм должен дать ответ h.
== Использование Heavy-light декомпозиции ==
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>. Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex>O(n), O(\log n)</tex> >.
== Алгоритм лестниц ==
=Longest path decomposition=
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v<\tex> в путь, идущий в самое глубокое поддерево,
т.е. в котором находится вершина с саомй большой глубиной.
Для каждой вершины сохраним номер пути в который она входит.
=Ladder decomposition=
Увеличим каждый путь в два раза вверх, для каждого ового пути сохраним все входящие в него вершины,
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас O(n) времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до <tex>O(n \logn)</tex>.
После этого посчитаем двоичные подьемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотику.
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
