186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
c) <tex>T(u) \cap T(v) = \emptyset </tex>
* Любой простой путь из вершины <math>v</math> в вершину <math>u</math> в дереве <math>t</math> содержит центроид <tex>c \in T(t)</tex>, такой что <tex>u, v \in T(c)</tex>.
|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>, ч.т.д.
Второе свойство очевидно из построения дерева <math>T</math>, т.к. если вершина принадлежит дереву центроидов <math>T</math>, то она является центроидом, а из построения <math>T</math> мы знаем, что каждая вершина исходного дерева принадлежит и дереву <math>T</math>.
Третье свойство - прямое следствие первых двух, т.к. вершина принадлежит любому центроиду <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> - дерево. Т.к. <math>T(u)</math> и <math>T(v)</math> - поддеревья различных вершин дерева <math>T</math>, то либо они не пересекаются, либо <math>u</math> - предок <math>v</math>, и значит <tex>T(v) \subset T(u)</tex>, либо <math>v</math> - предок <math>u</math>, и значит <tex>T(u) \subset T(v)</tex>.
Для доказательства последнего свойства выберем в качестве вершины <math>c</math> <math>lca(u, v)</math> в дереве центроидов <math>T</math>. Покажем, что так выбранная вершина <math>c</math> удовлетворяет заявленным свойствам. Для доказательства того, что <math>c</math> лежит на пути из <math>u</math> в <math>v</math> воспользуемся свойством 4 центроидной декомпозиции.
}}
Решение :
Построим центроидную декомпозицию <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>u</math> в дереве <math>t</math> содержит центроид <tex>c \in T(t)</tex>, такой что <tex>u, v \in subtree(c)</tex>.|proof=Докажем то, что в качестве c мы можем взять <math>lca(u, v)</math> в дереве <math>T(t)</math> центроидов. Действительно, во}}
== Варианты реализации ==
