186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devide&conqure - деревом отрезков. В предыдущем пункте мы определили статический оналог devide&conqure для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition="Деревом центроидов (или центроидной декомпозицией)" дерева <math>t</math> называют дерево <math>T</math>, построенное на вершинах дерева <math>t</math> следующим образом :
* Пусть вершина <math>с</math> - центроид дерева <math>t</math>. Объявим его корнем нового дерева <math>T</math>.
* Пусть при удалении вершины <math>c</math> из дерева <math>t</math> оно распалось на поддеревья <math>t_1, t_2,..., t_k</math>, а центроиды этих поддеревьев - вершины <math>c_1, c_2, ..., c_k</math> исходного дерева, соответственно. Проведем ребра из вершины <math>c</math> в дереве <math>T</math> ребра во все вершины <math>c_1, c_2,..., c_k</math>.
* Рекурсивно перейдем к построению для поддеревьев <math>t_1, t_2,..., t_k</math>.
}}
== Варианты реализации ==
