Изменения
Нет описания правки
== Введение ==
Рассмотрим <math>2</math> задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):
Задача <math>1</math>:
{{Задача
|definition = Есть массив <tex>a</tex> положительных целых чисел из <tex>n</tex> элементов. Также дано число <tex>W \geqslant 0</tex> и число <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> индексов массива, таких что <tex>|j - i| \leqslant l </tex> и <tex>\sum\limits_{k=i}^{j} a_k \leqslant W</tex>.
В любом дереве <math>t</math> существует центроид.
|proof=
Рассмотрим корень дерева <math>(r)</math>. Положим изначально <math>v = r</math>. Изначально <math>|subtree(v)| = n</math>. Среди всех детей <math>v</math> выберем вершину <math>u</math> с максимальным размером поддерева. Если <math>v</math> {{---}} не центроид, то положим <math>v = u</math> и продолжим выбор нового <math>u</math>, иначе {{---}} остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в произвольный момент времени <math>v</math> {{---}} не центроид и размер её наддерева меньше <math>\dfrac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\dfrac{n}{2}</math>, то есть <math>|subtree(u)| > \dfrac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \dfrac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, так как наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u)</math>. По индукции получаем, что в любой момент времени размер наддерева вершины <math>v </math> меньше <math>\dfrac{n}{2}</math>, значит мы будем спускаться только вниз по дереву <math>t</math>, и при переходе к вершине <math>u</math> {{---}} сыну <math>v</math> размер максимального поддерева уменьшится как минимум на <math>1</math>. Значит не более чем за <math>n</math> шагов наши действия прекратятся и мы окажемся в центроиде дерева <math>t</math>.
Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.
}}
{{Определение
|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>.
}}
С помощью описанных свойств дерева <math>T</math> мы можем решить задачу <math>2 </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>. Если изначально предпосчитать проходом [[Обход_в_глубину,_цвета_вершин| <math>dfs</math>]] величины <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> времени на запрос. Теперь научимся отвечать на запросы. Из последнего свойства центроидной декомпозиции видно, что если <math>u</math> {{---}} искомая ближайшая помеченная вершина к <math>v</math>, то путь между ними содержит центроид <math>c</math>, такой что <tex>u, v \in T(c)</tex>, причем <math>c</math> {{---}} предок одновременно вершин <math>u, v</math> в дереве<math>T</math>. Поэтому заведем [[Красно-черное_дерево|двоичное дерево поиска]] для каждого центроида <math>c \in T</math>. В этой структуре для каждой вершины <math>c</math> будем хранить пары <math>(len(c, u), u)</math> для всех помеченных вершин <math>u</math> в поддереве центроидов <math>T(c)</math>. Когда приходит запрос пометить вершину <math>v</math> {{---}} добавим в структуру данных для всех предков <math>p_c</math> вершины <math>v</math> в дереве <math>T</math> пары <math>(len(p_c, v), v)</math>. Мы совершим <math>O(\log(n))</math> добавлений, затратив <math>O(\log(n))</math> действий на каждое. Запрос снятия пометки с вершины обрабатывается аналогичными удалениями. Запрос поиска ближайшей к <math>v</math> помеченной вершины {{---}} это запрос поиска вершины <math>u</math>, такой что величина <math>len(c, u) + len(c, v)</math> минимальна, где <math>c</math> {{---}} предок <math>v</math> в дереве центроидов (по пятому свойству, нас интересуют именно такие <math>c)</math>. Этот запрос занимает так же <tex>O(log^2(n))</tex> времени.
