Изменения

Перейти к: навигация, поиск

Level Ancestor problem

3 байта добавлено, 18:46, 18 мая 2019
Ladder decomposition
=== Ladder decomposition ===
Это улучшение LongLongest-path декомпозиции, позволяющее, как мы потом докажем, подниматься на любую высоту за <tex>O(1)</tex>. Выполним его следующим образом: увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас <tex>O(n)</tex> времени (обход в глубину), соответственно удлиннение каждого пути ухудшит асимптотику до <tex>O(n \log n)</tex>.
36
правок

Навигация