186
правок
Изменения
→Статическая центроидная декомпозиция
Для решения новой задачи применим ту же идею, что и была до этого - разделяй и властвуй. Для этого нам потребуется следующий объект :
{{ОпределениеОпределени
|id=191213
|definition =
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,..., t_k</tex>, таких что для каждого <math>i</math> : <tex>|t_i| \leqslant \frac{n}{2}</tex>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
}}
Итак, в случае дерева идея разделяй-и-властвуй из предыдущего пункта будет формулироваться так : найдем центроид (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,..., t_k</tex>, после чего попытаемся найти недостающие пары вершин, находящиехя в разных поддеревьях и удовлетворяющих вопросу задачи. Для этого будем отвечать на следующие запросы : пусть мы сейчас считаем все пары, где первая из вершин находится в поддереве <math>t_i</math> и мы в некоторой структуре данных <math>S</math> храним все вершины остальных деревьев (каждую вершину задаем парой <math>(depth(v), length(v))</math> - глубина вершины и длина пути до нее из корня поддерева), расстояние до которых от корня их поддерева не превышает <math>min(l, n)</math>. Тогда просто пройдемся по всем вершинам <math>u</math> поддерева <math>t_i</math> и прибавим к ответу число вершин в структуре <math>S</math>, таких, что <tex>depth(u) \leqslant l - depth(v)</tex> и <tex>length(u) \leqslant l - length(v)</tex>. Это двумерные запросы, на которые можно отвечать за <math>O(log^2(n)</math> с помощью [[Многомерное_дерево_отрезков|2d-дерева отрезков]], либо за <math>O(log(n))</math> с помощью [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)|техники поиска точек в d-мерном пространстве]]. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.
=== Алгоритм Лемма о существовании центроида и алгоритм его нахождения центроида в произвольном . ==={Теорема|statement=В любом дереве t существует центроид.|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> и продолжим выбор нового u, иначе - остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в призвольный момент времени <math>v</math> - не центроид и размер её наддерева меньше <math>\frac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\frac{n}{2}</math>, т.е. <math>|subtree(u)| > \frac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \frac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\frac{n}{2}</math>, значит мы будем спускаться только вниз по дереву <math>t</math>, и при переходе к вершине <math>u</math> - сыну <math>v</math> размер максимального поддерева уменьшится как минимум на <math>1</math>. Значит не более чем за <math>n</math> шагов наши действия прекратятся и мы окажемся в центроиде дерева <math>t</math>, ч.т.д. Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.}}
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
