Изменения
Нет описания правки
Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас <tex>O(n) </tex> времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику до <tex>O(n \log n)</tex>.
=== Двоичные подъемы ===
После этого посчитаем двоичные подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотику.
