Изменения

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

Level Ancestor problem

263 байта добавлено, 18:43, 18 мая 2019
Longest path decomposition
== Алгоритм лестниц ==
=== Longest path decomposition ===
Разобьем все Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины на пути в ее ребенка с самым глубоким поддеревом.Сделаем ее следующим образом. Обойдем : обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
т.е. в котором находится вершина с самой большой глубиной.
Для каждой вершины сохраним номер пути в который она входит.
 
=== Ladder decomposition ===
Увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины,
36
правок

Навигация