36
правок
Изменения
→Longest path decomposition
== Алгоритм лестниц ==
=== Longest path decomposition ===
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
т.е. в котором находится вершина с самой большой глубиной.
Для каждой вершины сохраним номер пути в который она входит.
=== Ladder decomposition ===
Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,