186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.
* Каждая вершина <math>v</math> дерева <math>t</math> является центроидом одного из поддеревьев дерева <math>T</math>
* Каждая вершина дерева <math>t</math> принадлежит <math>O(log(n))</math> поддеревьям дерева <math>T</math> (еще говорят, что вершина принадлежит <math>O(log(n))</math> центроидам дерева <math>t</math>, или что эти центроиды содержат вершину)
|proof=
Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\frac{|subtree(c)|}{2}</tex>, то при спуске в каждую следующую вершину на пути к любому листу в дереве <math>T</math> размер поддерева вершины, в которой мы сейчас находимся, уменьшается как минимум на <math>2</math>. Значит длина всего пути до листа не превосходит <math>log(n)</math>, ч.т.д.
{{Задача
|definition = Есть страна, дерево <math>nt</math> городов которой связаны двустронними дорогами, причем так, чтобы получился минимальный связный граф на из <math>n-1</math> ребрахвершин. В каждом городе есть госпиталь, который в каждый момент времени любая вершина дерева может быть либо открытпомечена, либо закрытнет. Изначально помечена только вершина номер 0. Дан список из <math>m</math> событий запросов : * Госпиталь в городе Вершину <math>v</math> открылсяпометили.* Госпиталь в городе С вершины <math>v</math> закрылсясняли пометку.* Больной из города Найти номер ближайшей к <math>v</math> хочет узнать номер ближайшего города, госпиталь которого открытпомеченной вершины.
}}
Решение :
Построим центроидную декомпозицию <math>T</math> дерева городов <math>t</math>. Изначально посчитаем для каждого центроида, содержащего вершину <math>0</math> посчитаем расстояние до вершины <math>0</math>. Для этого воспользуемся [[Метод_двоичного_подъема|методом двоичных подъемов для поиска lca пары вершин в дереве]], а также тем фактом, что если глубина <math>h(v)</math> вершины <math>v</math> в дереве определена как расстояние от корня до вершины <math>v</math>, то длина пути между парой вершин <math>(u, v)</math> есть <tex>len(u, v) = h(u) + h(v) - 2 \cdot h(lca(u, v))</tex>. Если изначально предпосчитать проходом [[Обход_в_глубину,_цвета_вершин| dfs]] величины <math>h(v)</math> за <math>O(n)</math>, то ответ на запрос <math>len(u,v)</math> можно делать за время <math>O(log(n))</math> с <tex>O(n \cdot log(n))</tex>доп. памятью. Также можно воспользоваться техникой [[Сведение_задачи_LCA_к_задаче_RMQ|сведения задачи LCA к RMQ]] и решить с <math>O(n)</math> дополнительной памятью и <math>O(1)</math> времени на запрос. Теперь научимся отвечать на запросы. Для этого нам понадобится следующее утверждение.{{Лемма|statement=Кратчайший путь из любой вершины <math>v</math> до любой помеченной вершины в дереве <math>t</ TODO :: дописать решение math> проходит через какой-то центроид <math>с \in T(мой код : https:t)</math>, такой что <math>c</math> содержит обе вершины (вершину <math>v</drivenotepadmath> и ближайшую к ней помеченную).github|proof=Предположим, что вершина <math>u</math> - ближайшая к <math>v</math> среди помеченных.ioТогда кратчайший путь между <math>u</math> и <math>v</appmath> состоит из двух промежутков - пути <math>v -> lca(u, v)</?state={%22action%22:%22open%22math> и пути <math>lca(u,%22ids%22:[%220Bw29IKNdcznCYnVFbVo2alZiSzA%22]v) -> u</math>. }})
== Варианты реализации ==
