186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
* Пусть при удалении вершины <math>c</math> из дерева <math>t</math> оно распалось на поддеревья <tex>t_1, t_2,..., t_k</tex>, тогда детьми вершины c объявим <tex>T(t_1), T(t_t),..., T(t_k)</tex>.
}}
=== Свойства центроидной декомпозиции ===
{{Лемма
|statement=
С помощью описанных свойств дерева <math>T</math> мы можем решить задачу 2 для дерева :
=== Пример решения задачи с помощью центроидной декомпозиции ===
{{Задача
|definition = Есть дерево <math>t</math> из <math>n</math> вершин. В каждый момент времени любая вершина дерева может быть либо помечена, либо нет. Изначально помечена только вершина номер 0. Дан список из <math>m</math> запросов :
