Изменения

Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex>O(n), O(\log n)</tex> >.

== Алгоритм лестниц ==

Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине

<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,

т.е. в котором находится вершина с саомй большой глубиной.

Для каждой вершины сохраним номер пути в который она входит.

Увеличим каждый путь в два раза вверх, для каждого ового пути сохраним все входящие в него вершины,

а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у