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