186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
Третье свойство - прямое следствие первых двух, т.к. вершина принадлежит любому центроиду <math>c</math> т.и т.т., когда c - отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.
}}
С помощью описанных свойств дерева <math>T</math> мы можем решить задачу 2 для дерева :
{{Задача
|definition = Есть страна, <math>n</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на <math>n-1</math> ребрах. В каждом городе есть госпиталь, который в каждый момент времени может быть либо открыт, либо закрыт. Дан список из <math>m</math> событий :
* Госпиталь в городе <math>v</math> открылся.
* Госпиталь в городе <math>v</math> закрылся.
* Больной из города <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открыт.
}}
Решение :
Построим центроидную декомпозицию <math>T</math> дерева городов <math>t</math>,
== Варианты реализации ==
