Изменения
Нет описания правки
Центроидная декомпозиция (англ. ''centroid decomposition'') {{---}} это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.
== Введение ==
{{Определение
|definition=
'''Деревом центроидов''' (или центроидной декомпозицией, англ. '''centroid decomposition tree''') дерева <math>t</math> называют дерево <math>T(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,\dots, t_k</tex>, тогда детьми вершины c объявим <tex>T(t_1), T(t_t),\dots, T(t_k)</tex>.
