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