Изменения
Нет описания правки
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
т.е. в котором находится вершина с саомй самой большой глубиной.
Для каждой вершины сохраним номер пути в который она входит.
=== Ladder decomposition ===
Увеличим каждый путь в два раза вверх, для каждого ового нового пути сохраним все входящие в него вершины,
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас O(n) времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до <tex>O(n \log n)</tex>.
=== Двоичные подъемы ===После этого посчитаем двоичные подьемы подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотику.
Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.
*Сделаем один максимально большой прыжок вверх с помощью насчитанных двоичных подъемов.
#<tex>i = \log k</tex>
#<tex>v = p_i[v]</tex>
* Рассмотрим путь, на котором лежит вершина <tex>v</tex> до удвоения. Он длины хотя бы <tex>2^i</tex>, так как мы точно знаем, что существует вершина потомок <tex>v</tex>, расстояние до которого ровно <tex>2^i</tex> (это вершина, из которой мы только что пришли). Значит, после удвоения этот путь стал длины хотя бы <tex>2^{i + 1}</tex>, причем хотя бы <tex>2^i</tex> вершин в нем - предки <tex>v</tex>. Это означает, что вершина, которую мы ищем, находится на этом пути (иначе бы мы могли до этого прыгнуть еще на <tex>2^i</tex> вверх). Так как мы знаем позицию <tex>v</tex> в этом пути, то нужную вершину мы можем найти за <tex>O(1)</tex>.
Таким образом, наш алгоритм работает за < <tex>O(n\log n), O(1)</tex> >. С помощью метода четырех русских данный метод можно улучшить до < <tex>O(n), O(1)</tex> > с помощью оптимизации предподсчета.
