Centroid decomposition — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Динамическая центроидная декомпозиция (дерево центроидной декомпозиции))
м (rollbackEdits.php mass rollback)
 
(не показаны 82 промежуточные версии 8 участников)
Строка 1: Строка 1:
Centroid decomposition (рус. центроидная декомпозиция) - это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.
+
Центроидная декомпозиция (англ. ''centroid decomposition'') {{---}} это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.
  
 
== Введение ==
 
== Введение ==
Рассмотрим 2 задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):
+
Рассмотрим <math>2</math> задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):
  
Задача 1
+
Задача <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_{i=0}^{n - 1} a_i \leqslant W</tex>.
+
|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>.
 
}}
 
}}
Задача 2:
+
Задача <math>2</math>:
 
{{Задача
 
{{Задача
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида :
+
|definition = Есть прямая дорога, на которой расположены <tex>n</tex> городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида:
* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, что <tex>|u - v|</tex> минимально возможное.
+
* дан город <tex>v</tex>, в котором находится больной и требуется найти такой город <tex>u</tex>, который может принимать больных и <tex>|u - v|</tex> минимально возможное.
 
* дан город <tex>v</tex> и сказано, что больше он не будет принимать больных
 
* дан город <tex>v</tex> и сказано, что больше он не будет принимать больных
 
* дан город <tex>v</tex> и сказано, что теперь он может принимать больных
 
* дан город <tex>v</tex> и сказано, что теперь он может принимать больных
 
}}
 
}}
 
Для начала решим обе задачи.  
 
Для начала решим обе задачи.  
Первая задача решается методом [[Сортировка_слиянием|qevide&conqure (рус. разделяй и властвуй)]] - давайте разделим массив <tex>a[0...n-1]</tex> на 2 массива <tex>a[0...\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2}...n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j \geqslant \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой - методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{\frac{n}{2} + 1} a_j</tex>) - для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \frac{n}{2} - l + 1, p_2 = \frac{n}{2}</tex>. Пока <tex>p_2 - 1> \frac{n}{2}</tex> и
+
Первая задача решается методом [[Сортировка_слиянием|«разделяй и властвуй»]] {{---}} давайте разделим массив <tex>a[0 \dots n-1]</tex> на 2 массива <tex>a[0\dots\dfrac{n}{2} - 1]</tex> и <tex>a[\dfrac{n}{2} \dots n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \dfrac{n}{2},\text{ }j \geqslant \dfrac{n}{2}</tex>. Для этого воспользуемся другой известной техникой {{---}} методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum\limits_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных <tex>(suf[i] = \sum\limits_{j=i}^{\frac{n}{2} + 1} a_j)</tex> {{---}} для левой. Заведем два указателя <tex>(p_1</tex> и <tex>p_2)</tex>. Изначально установим <tex>p_1 = \dfrac{n}{2} - l + 1,\text{ }p_2 = \dfrac{n}{2}</tex>. Пока <tex>p_2 - 1> \dfrac{n}{2}</tex> и
  
<tex>pref[p_2] + suf[p_1] > W </tex> будем уменьшать <math>p_2</math> на <math>1</math>. Если после этого <math>pref[p_2] + suf[p_1] \leqslant W</math>, то к ответу прибавим <math>(p_2 - \frac{n}{2} + 1) * (\frac{n}{2} - p_1)</math>, посго, увеличим <math>p_1</math> на <math/math>. Так будем делать, пока <math>p_1 < \frac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива - получим ответ на задачу. Асимптотика такого алгоритма : <tex>T(n) = 2 * T(n / 2) + O(n) = O(n)</tex>
+
<tex>pref[p_2] + suf[p_1] > W </tex> будем уменьшать <math>p_2</math> на <math>1</math>. Если после этого <math>pref[p_2] + suf[p_1] \leqslant W</math>, то к ответу прибавим <math>(p_2 - \dfrac{n}{2} + 1) \cdot (\dfrac{n}{2} - p_1)</math>, после чего увеличим <math>p_1</math> на <math>1</math>. Так будем делать, пока <math>p_1 < \dfrac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива {{---}} получим ответ на задачу. Время работы такого алгоритма: <tex>T(n) = 2 \cdot T(n / 2) + O(n) = O(n*log(n))</tex>
  
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure - [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
+
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию «разделяй и властвуй» {{---}} [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
поддерживающее 2 вида запросов : присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b</math>, такой что <tex>b_i = 0</tex>, если в i-м городе принимает госпиталь и <tex>b_i = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь - делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей :  
+
поддерживающее 2 вида запросов: присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b</math>, такой что <tex>b_i = 0</tex>, если в <math>i</math>-м городе принимает госпиталь и <tex>b_i = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь {{---}} делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайший госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей:  
а) (<tex>O(n \cdot log^2(n)</tex>) Бинарным поиском ищем ближайший слева и ближайший справа к i-му городу госпиталь (такой город <math>j</math>, что <tex>\min\limits_{k=i..j}b_k= 1</tex>). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков.   
+
* <tex>(O(n \cdot log^2(n))</tex> Бинарным поиском ищем ближайший слева и ближайший справа к <math>i</math>-му городу госпиталь (такой город <math>j</math>, что <tex>\min\limits_{k=i..j}b_k= 1)</tex>. Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков.   
б) (<tex>O(n \cdot log(n)</tex>) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.
+
* <tex>(O(n \cdot \log(n))</tex> Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновременно и бинарный поиск, и спуск/подъем по дереву.
  
 
== Статическая центроидная декомпозиция ==
 
== Статическая центроидная декомпозиция ==
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
+
Перейдем к обобщению поставленных задач на случай дерева.
 
{{Задача
 
{{Задача
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов.
+
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W \geqslant 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов<ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160324a1.pdf  Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>.
 
}}
 
}}
  
Для решения новой задачи применим ту же идею, что и была до этого - разделяй и властвуй. Для этого нам потребуется следующий объект :
+
Для решения новой задачи применим ту же идею, что и была до этого {{---}} «разделяй и властвуй». Для этого нам потребуется следующий объект:
  
 
{{Определение
 
{{Определение
 
|id=191213
 
|id=191213
 
|definition =
 
|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>, т.е. размер каждого поддерева не превосходит половины размера исходного дерева.
+
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько <math>(k)</math> поддеревьев <tex>t_1, t_2,\dots, t_k</tex>, таких что для каждого <math>i</math>: <tex>|t_i| \leqslant \dfrac{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-мерном пространстве]]. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.
+
Итак, в случае дерева идея «разделяй и властвуй» из предыдущего пункта будет формулироваться так: [[#l1|найдем центроид]]. Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> {{---}} размер дерева. Тогда, как и в упрощенной версии задачи {{---}} рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,\dots, 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-мерном пространстве]]. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.
  
Оценим итоговую асимптотику : <tex>T(n) = k * T(n / k) + O(n \cdot log(n))</tex>. Решая это рекурентное соотношение, получим <math>O(n \cdot log(n))</math>.
+
Оценим итоговое время работы алгоритма: <tex>T(n) = k \cdot T(n / k) + O(n \cdot \log(n))</tex>. Решая это рекуррентное соотношение, получим <math>O(n \cdot \log(n))</math>.
  
Теперь, как и было обещено, докажем лемму о существовании центроида и опишем алгоритм его эффективного поиска.
+
Теперь докажем лемму о существовании центроида и опишем алгоритм его эффективного поиска.
  
 
=== Лемма о существовании центроида и алгоритм его нахождения. ===
 
=== Лемма о существовании центроида и алгоритм его нахождения. ===
{{Лемма
+
{{Лемма|id=l1
 
|statement=
 
|statement=
В любом дереве t существует центроид.
+
В любом дереве <math>t</math> существует центроид.
 
|proof=
 
|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>, ч.т.д.
+
Рассмотрим корень дерева <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>.
 
Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.  
 
Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.  
 
}}
 
}}
 +
 
=== Реализация ===
 
=== Реализация ===
  
 
Поиск центроида в дереве:
 
Поиск центроида в дереве:
  
   '''int''' <tex>\mathtt{findCentroid}</tex>('''int[]''' children[n], '''int''' v, '''int''' sz[n])
+
   '''int''' <tex>\mathtt{findCentroid}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz, '''int''' tree_size)
 
     max_subtree = -1
 
     max_subtree = -1
 
     '''for''' u : children(v)
 
     '''for''' u : children(v)
           '''if''' sz[u] > sz[v] / 2 and sz[u] > sz[max_subtree] <font color=green>// считаем sz[-1] = 0 </font >
+
           '''if''' sz[u] > tree_size / 2 '''and''' sz[u] > sz[max_subtree] <font color=green>// считаем sz[-1] = 0 </font >
 
               max_subtree = u
 
               max_subtree = u
 
     '''if''' max_subtree == -1
 
     '''if''' max_subtree == -1
 
           return v
 
           return v
 
     '''else'''  
 
     '''else'''  
           '''return''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz)
+
           '''return''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, tree_size)
  
 
Шаблон решения произвольной задачи на статическую центроидную декомпозицию:
 
Шаблон решения произвольной задачи на статическую центроидную декомпозицию:
  
   <tex>\mathtt{solve}</tex>('''int[]''' children[n], '''int''' v, '''int''' sz[n])
+
   <tex>\mathtt{solve}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz)
     c = <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz) <font color=green>// находим c - центроид поддерева вершины v </font >
+
     c = <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, sz[v]) <font color=green>// находим c {{---}} центроид поддерева вершины v </font >
 
     ch = children[c]
 
     ch = children[c]
     <tex>\mathtt{deleteEdges}</tex>(c, children) <font color=green>// удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с. Это полезно делать, если решение подзадачи для поддерева предполагает проход dfs </font >
+
     <tex>\mathtt{deleteEdges}</tex>(c, children) <font color=green>// удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с.  
 +
        Это полезно делать, если решение подзадачи для поддерева предполагает проход <math>dfs</math> </font >
 
     '''for''' c2 : ch[c]
 
     '''for''' c2 : ch[c]
 
           <tex>\mathtt{solve}</tex>(children, c2, sz)
 
           <tex>\mathtt{solve}</tex>(children, c2, sz)
Строка 77: Строка 79:
  
 
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
 
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devide&conqure - деревом отрезков. В предыдущем пункте мы определили статический оналог devide&conqure для дерева. Теперь обобщим этот метод для динамических задач.
+
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией «разделяй и властвуй» {{---}} деревом отрезков. В предыдущем пункте мы определили статический аналог «разделяй и властвуй» для дерева. Теперь обобщим этот метод для динамических задач.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Деревом центроидов (или центроидной декомпозицией)''' дерева <math>t</math> называют дерево <math>T</math>, построенное на вершинах дерева <math>t</math> следующим образом :
+
'''Деревом центроидов''' (или центроидной декомпозицией, англ. ''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>. Объявим его корнем нового дерева <math>T</math>.
* Пусть при удалении вершины <math>c</math> из дерева <math>t</math> оно распалось на поддеревья <tex>t_1, t_2,..., t_k</tex>, а центроиды этих поддеревьев - вершины <tex>c_1, c_2, ..., c_k</tex> исходного дерева, соответственно. Проведем из вершины <math>c</math> в дереве <math>T</math> ребра во все вершины <tex>c_1, c_2,..., c_k</tex>.
+
* Пусть при удалении вершины <math>c</math> из дерева <math>t</math> оно распалось на поддеревья <tex>t_1, t_2,\dots, t_k</tex>, тогда детьми вершины c объявим <tex>T(t_1), T(t_2),\dots, T(t_k)</tex>.
* Рекурсивно перейдем к построению для поддеревьев <tex>t_1, t_2,..., t_k</tex>.
 
 
}}
 
}}
 
+
=== Свойства центроидной декомпозиции ===
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Свойства центроидной декомпозиции :
+
'''Свойства центроидной декомпозиции''':
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.  
+
# Глубина дерева центроидов не превосходит <tex>\\log(n)</tex>.  
* Каждая вершина <math>v</math> дерева <math>t</math> является центроидом одного из поддеревьев дерева <math>T</math>
+
# Каждая вершина <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>, или что эти центроиды содержат вершину)
+
# Каждая вершина дерева <math>t</math> принадлежит <math>O(\log(n))</math> поддеревьям дерева <math>T</math> (еще говорят, что вершина принадлежит <math>O(\log(n))</math> центроидам дерева <math>t</math>, или что эти центроиды содержат вершину)
 +
# Для любых вершин <tex>u, v \in T (u \neq v)</tex> верно ровно одно из следующих трех утверждений:
 +
#*<tex>T(v) \subset T(u)</tex>
 +
#* <tex>T(u) \subset T(v)</tex>
 +
#* <tex>T(u) \cap T(v) = \emptyset </tex>
 +
# Простой путь между любой парой вершин <math>u, v</math> в дереве <math>t</math> содержит центроид <tex>c \in T(t)</tex>, такой что <tex>u, v \in T(c)</tex>.
 
|proof=
 
|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>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\dfrac{|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>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>c</math> т.и т.т., когда <math>c</math> {{---}} отец вершины <math>v</math> в дереве центроидов. Так как вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство <math>2</math>), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству <math>1</math> длина любого вертикального (и даже простого) пути есть <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> удовлетворяет заявленным свойствам. То, что <tex>u, v \in T(c)</tex> {{---}} очевидно по определению <math>lca</math>, так как каждый предок любой вершины в дереве центроидов содержит эту вершину. Теперь докажем, что <math>c</math> лежит на пути между парой вершин <math>u, v</math>. Так как <math>c = lca(u, v)</math> в <math>T</math>, то из <math>c</math> нет ребра в такого сына, который содержит одновременно <math>u</math> и <math>v</math> в своем поддереве (в дереве <math>T)</math>, значит после удаления <math>c</math> дерево <math>t</math> разделится на несколько поддеревьев, таких что вершины <math>u</math> и <math>v</math> окажутся в разных компонентах связности. А значит найдется такое ребро <math>(c, x)</math>, которое принадлежало пути из <math>u</math> в <math>v</math>, но после удаления <math>c</math> удалилось. Это доказывает то, что вершина <math>c</math> лежала на пути из <math>u</math> в <math>v</math>.
 
}}
 
}}
  
С помощью описанных свойств дерева <math>T</math> мы можем решить задачу 2 для дерева :
+
С помощью описанных свойств дерева <math>T</math> мы можем решить задачу <math>2</math> для дерева:
  
 +
=== Пример решения задачи с помощью центроидной декомпозиции ===
 
{{Задача
 
{{Задача
|definition = Есть дерево <math>t</math> из <math>n</math> вершин. В каждый момент времени любая вершина дерева может быть либо помечена, либо нет. Изначально помечена только вершина номер 0. Дан список из <math>m</math> запросов :  
+
|definition = Есть дерево <math>t</math> из <math>n</math> вершин. В каждый момент времени любая вершина дерева может быть либо помечена, либо нет. Изначально помечена только вершина номер <math>0</math>. Дан список из <math>m</math> запросов:  
 
* Вершину <math>v</math> пометили.
 
* Вершину <math>v</math> пометили.
 
* С вершины <math>v</math> сняли пометку.
 
* С вершины <math>v</math> сняли пометку.
* Найти номер ближайшей к <math>v</math> помеченной вершины.
+
* Найти номер ближайшей к <math>v</math> помеченной вершины<ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160324a1.pdf  Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>.
 
}}
 
}}
  
Решение :
 
  
Построим центроидную декомпозицию <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>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> времени.
Кратчайший путь из любой вершины <math>v</math> до любой помеченной вершины в дереве <math>t</math> проходит через какой-то центроид <math>с \in T(t)</math>, такой что <math>c</math> содержит обе вершины (вершину <math>v</math> и ближайшую к ней помеченную).
+
 
|proof=
+
Итак, мы научились решать задачу с <math>O(n)</math> дополнительной памятью и временной сложностью <math>O(log^2(n))</math> на запрос любого типа с предварительным предпосчетом за <math>O(n)</math>.
Предположим, что вершина <math>u</math> - ближайшая к <math>v</math> среди помеченных. Тогда кратчайший путь между <math>u</math> и <math>v</math> состоит из двух промежутков - пути <math>v -- lca(u, v)</math> и пути <math>lca(u, v) -- u</math>.  
+
 
}}
+
== Варианты хранения центроидной декомпозиции ==
 +
Для хранения дерева центроидов <math>T</math> есть <math>2</math> подхода, имеющих свои преимущества и недостатки:
 +
* Для каждой вершины <math>v</math> исходного дерева запомним величину <math>p_v</math> {{---}} номер предка вершины <math>v</math> в дереве <math>T</math>.
 +
 
 +
Этот подход наиболее экономный по памяти <math>(O(n))</math>, но уступает в скорости и функциональности.
 +
 
 +
* Для каждой вершины <math>v</math> исходного дерева будем хранить весь массив предков <math>p[v]</math> в дереве центроидов.
 +
 
 +
Этот подход уступает в количестве необходимой дополнительной памяти <tex>(O(n \cdot \log(n))</tex> суммарно), но имеет ряд преимуществ:
  
== Варианты реализации ==
+
#При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, так как весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован
// TODO :: написать про то, что можно хранить предков (+память О(n), - скорость, - ничего нельзя сделать), а можно для каждой вершины - массив содержащих ее центроидов (+скорость(кэш), +масштабируемость(структуры данных на путях), - память n*logn)
+
# На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков <math>O(log(\log(n)))</math> на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за <math>O(\log(\log(n))</math> на запрос, так как размер массива предков есть <math>O(\log(n))</math> (по свойству <math>1</math> центроидной декомпозиции). Используя эту оптимизацию можно получить время <math>O(\log(n)) + O(\log(\log(n)) = O(\log(n))</math> на запрос нахождения ближайшей помеченной вершины. Чтобы добиться улучшенной асимптотики для запросов изменения можно хранить дерево отрезков на каждом из путей <math>p[v]</math>, в каждой вершине которого хранить двоичное дерево поиска и поддерживать отложенные операции. Тогда ответ на эти запросы будет занимать <math>O(\log(n) \cdot \log(\log(n))</math> времени.
  
 
==См. также==
 
==См. также==
Строка 126: Строка 142:
 
*[[:Метод_двоичного_подъема| Метод двоичного подъема]]
 
*[[:Метод_двоичного_подъема| Метод двоичного подъема]]
  
== Примечания ==
+
== Примечания ==  
 
<references/>
 
<references/>
 +
 +
==Источники информации==
 +
* [https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree  Quora {{---}} Centroid Decomposition of a Tree]
 +
* [http://acm.math.spbu.ru/~sk1/mm/lections/zksh2016-centroid/conspect.pdf  ЗКШ {{---}} Конспект лекции про центроидную декомпозицию]
 +
* [https://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-roi-2015-analysis.pdf  Разбор задач РОИ 2015]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]

Текущая версия на 19:26, 4 сентября 2022

Центроидная декомпозиция (англ. centroid decomposition) — это структура данных, позволяющая отвечать на запросы на дереве. Чаще всего это запросы, связанные с нахождением функции на вершинах, связанных неравенством на расстояние между ними в дереве. Также иногда применяется для запросов на путях в дереве.

Введение

Рассмотрим [math]2[/math] задачи на обычном массиве (в дальнейшем мы будем их обобщать на случай дерева):

Задача [math]1[/math]:

Задача:
Есть массив [math]a[/math] положительных целых чисел из [math]n[/math] элементов. Также дано число [math]W \geqslant 0[/math] и число [math]l[/math]. Требуется найти количество пар [math](i, j)[/math] индексов массива, таких что [math]|j - i| \leqslant l [/math] и [math]\sum\limits_{k=i}^{j} a_k \leqslant W[/math].

Задача [math]2[/math]:

Задача:
Есть прямая дорога, на которой расположены [math]n[/math] городов. В некоторых городах есть госпитали, которые могут принимать больных. Поступают запросы вида:
  • дан город [math]v[/math], в котором находится больной и требуется найти такой город [math]u[/math], который может принимать больных и [math]|u - v|[/math] минимально возможное.
  • дан город [math]v[/math] и сказано, что больше он не будет принимать больных
  • дан город [math]v[/math] и сказано, что теперь он может принимать больных

Для начала решим обе задачи. Первая задача решается методом «разделяй и властвуй» — давайте разделим массив [math]a[0 \dots n-1][/math] на 2 массива [math]a[0\dots\dfrac{n}{2} - 1][/math] и [math]a[\dfrac{n}{2} \dots n-1][/math] и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар [math](i, j)[/math], таких что [math]i \lt \dfrac{n}{2},\text{ }j \geqslant \dfrac{n}{2}[/math]. Для этого воспользуемся другой известной техникой — методом двух указателей. Посчитаем массив префиксных сумм для правой половины [math]pref[i] = \sum\limits_{j=\frac{n}{2}}^{i} a_j[/math] и суффиксных [math](suf[i] = \sum\limits_{j=i}^{\frac{n}{2} + 1} a_j)[/math] — для левой. Заведем два указателя [math](p_1[/math] и [math]p_2)[/math]. Изначально установим [math]p_1 = \dfrac{n}{2} - l + 1,\text{ }p_2 = \dfrac{n}{2}[/math]. Пока [math]p_2 - 1\gt \dfrac{n}{2}[/math] и

[math]pref[p_2] + suf[p_1] \gt W [/math] будем уменьшать [math]p_2[/math] на [math]1[/math]. Если после этого [math]pref[p_2] + suf[p_1] \leqslant W[/math], то к ответу прибавим [math](p_2 - \dfrac{n}{2} + 1) \cdot (\dfrac{n}{2} - p_1)[/math], после чего увеличим [math]p_1[/math] на [math]1[/math]. Так будем делать, пока [math]p_1 \lt \dfrac{n}{2}[/math]. В конце сложим текущий ответ и ответы для половин массива — получим ответ на задачу. Время работы такого алгоритма: [math]T(n) = 2 \cdot T(n / 2) + O(n) = O(n*log(n))[/math]

Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию «разделяй и властвуй» — дерево отрезков. Построим дерево отрезков, поддерживающее 2 вида запросов: присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив [math]b[/math], такой что [math]b_i = 0[/math], если в [math]i[/math]-м городе принимает госпиталь и [math]b_i = 1[/math] иначе. Когда в каком-то городе открывается/закрывается госпиталь — делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайший госпиталь к [math]i[/math]-му городу, можно воспользоваться одной из следующих идей:

  • [math](O(n \cdot log^2(n))[/math] Бинарным поиском ищем ближайший слева и ближайший справа к [math]i[/math]-му городу госпиталь (такой город [math]j[/math], что [math]\min\limits_{k=i..j}b_k= 1)[/math]. Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков.
  • [math](O(n \cdot \log(n))[/math] Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновременно и бинарный поиск, и спуск/подъем по дереву.

Статическая центроидная декомпозиция

Перейдем к обобщению поставленных задач на случай дерева.

Задача:
Есть взвешенное дерево [math]t[/math] из [math]n[/math] вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа [math]W \geqslant 0[/math] и [math]l[/math]. Требуется найти количество пар [math](i, j)[/math] вершин дерева, таких что расстояние между ними не превосходит [math]l[/math] по числу ребер и не превосходит [math]W[/math] по сумме весов[1].


Для решения новой задачи применим ту же идею, что и была до этого — «разделяй и властвуй». Для этого нам потребуется следующий объект:


Определение:
Центроидом дерева (англ. centroid) называется такая вершина [math]v[/math] дерева [math]t[/math], после удаления которой дерево разбивается на несколько [math](k)[/math] поддеревьев [math]t_1, t_2,\dots, t_k[/math], таких что для каждого [math]i[/math]: [math]|t_i| \leqslant \dfrac{n}{2}[/math], то есть размер каждого поддерева не превосходит половины размера исходного дерева.

Итак, в случае дерева идея «разделяй и властвуй» из предыдущего пункта будет формулироваться так: найдем центроид. Предположим, что мы сумели найти центроид за [math]O(n)[/math], где [math]n[/math] — размер дерева. Тогда, как и в упрощенной версии задачи — рекурсивно найдем ответ для всех поддеревьев [math]t_1, t_2,\dots, t_k[/math], после чего попытаемся найти недостающие пары вершин, находящиеся в разных поддеревьях и удовлетворяющих вопросу задачи. Для этого будем отвечать на следующие запросы: пусть мы сейчас считаем все пары, где первая из вершин находится в поддереве [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], таких, что [math]depth(u) \leqslant l - depth(v)[/math] и [math]length(u) \leqslant l - length(v)[/math]. Это двумерные запросы, на которые можно отвечать за [math]O(log^2(n)[/math] с помощью 2d-дерева отрезков, либо за [math]O(\log(n))[/math] с помощью техники поиска точек в d-мерном пространстве. Также читателю предлагается придумать и более эффективные и простые способы решить эту подзадачу.

Оценим итоговое время работы алгоритма: [math]T(n) = k \cdot T(n / k) + O(n \cdot \log(n))[/math]. Решая это рекуррентное соотношение, получим [math]O(n \cdot \log(n))[/math].

Теперь докажем лемму о существовании центроида и опишем алгоритм его эффективного поиска.

Лемма о существовании центроида и алгоритм его нахождения.

Лемма:
В любом дереве [math]t[/math] существует центроид.
Доказательство:
[math]\triangleright[/math]

Рассмотрим корень дерева [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)| \gt \dfrac{n}{2}[/math], а значит размер "наддерева" вершины [math]u[/math] равен [math]n - |subtree(u)| \lt \dfrac{n}{2}[/math]. При этом теперь размер любого поддерева, на которое распадется дерево 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].

Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.
[math]\triangleleft[/math]

Реализация

Поиск центроида в дереве:

 int [math]\mathtt{findCentroid}[/math](int[] children[n], int v, int[] sz, int tree_size)
    max_subtree = -1
    for u : children(v)
         if sz[u] > tree_size / 2 and sz[u] > sz[max_subtree] // считаем sz[-1] = 0 
              max_subtree = u
    if max_subtree == -1
         return v
    else 
         return [math]\mathtt{findCentroid}[/math](children, max_subtree, sz, tree_size)

Шаблон решения произвольной задачи на статическую центроидную декомпозицию:

 [math]\mathtt{solve}[/math](int[] children[n], int v, int[] sz)
    c = [math]\mathtt{findCentroid}[/math](children, max_subtree, sz, sz[v]) // находим c — центроид поддерева вершины v 
    ch = children[c]
    [math]\mathtt{deleteEdges}[/math](c, children) // удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с. 
        Это полезно делать, если решение подзадачи для поддерева предполагает проход [math]dfs[/math] 
    for c2 : ch[c]
         [math]\mathtt{solve}[/math](children, c2, sz)
    [math]\mathtt{mergeSolution}[/math](children, c2) // решаем для текущего поддерева 

Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)

Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией «разделяй и властвуй» — деревом отрезков. В предыдущем пункте мы определили статический аналог «разделяй и властвуй» для дерева. Теперь обобщим этот метод для динамических задач.

Определение:
Деревом центроидов (или центроидной декомпозицией, англ. 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] оно распалось на поддеревья [math]t_1, t_2,\dots, t_k[/math], тогда детьми вершины c объявим [math]T(t_1), T(t_2),\dots, T(t_k)[/math].

Свойства центроидной декомпозиции

Лемма:
Свойства центроидной декомпозиции:
  1. Глубина дерева центроидов не превосходит [math]\\log(n)[/math].
  2. Каждая вершина [math]v[/math] дерева [math]t[/math] является центроидом одного из поддеревьев дерева [math]t[/math]
  3. Каждая вершина дерева [math]t[/math] принадлежит [math]O(\log(n))[/math] поддеревьям дерева [math]T[/math] (еще говорят, что вершина принадлежит [math]O(\log(n))[/math] центроидам дерева [math]t[/math], или что эти центроиды содержат вершину)
  4. Для любых вершин [math]u, v \in T (u \neq v)[/math] верно ровно одно из следующих трех утверждений:
    • [math]T(v) \subset T(u)[/math]
    • [math]T(u) \subset T(v)[/math]
    • [math]T(u) \cap T(v) = \emptyset [/math]
  5. Простой путь между любой парой вершин [math]u, v[/math] в дереве [math]t[/math] содержит центроид [math]c \in T(t)[/math], такой что [math]u, v \in T(c)[/math].
Доказательство:
[math]\triangleright[/math]
  1. Действительно, так как размер поддерева [math]s[/math] каждой вершины [math]c[/math] дереве [math]T[/math] не превосходит [math]\dfrac{|subtree(c)|}{2}[/math], то при спуске в каждую следующую вершину на пути к любому листу в дереве [math]T[/math] размер поддерева вершины, в которой мы сейчас находимся, уменьшается как минимум на [math]2[/math]. Значит длина всего пути до листа не превосходит [math]\log(n)[/math].
  2. Второе свойство очевидно из построения дерева [math]T[/math], так как если вершина принадлежит дереву центроидов [math]T[/math], то она является центроидом, а из построения [math]T[/math] мы знаем, что каждая вершина исходного дерева принадлежит и дереву [math]T[/math].
  3. Третье свойство — прямое следствие первых двух, так как вершина принадлежит любому центроиду [math]c[/math] т.и т.т., когда [math]c[/math] — отец вершины [math]v[/math] в дереве центроидов. Так как вершина [math]v[/math] точно принадлежит дереву [math]T[/math] (свойство [math]2[/math]), то она лежит на каком-то пути в дереве [math]T[/math], причем все ее родители (центроиды) ее содержат. А по свойству [math]1[/math] длина любого вертикального (и даже простого) пути есть [math]O(\log(n))[/math].
  4. Четвертое свойство очевидно из того, что [math]T[/math] — дерево. Так как [math]T(u)[/math] и [math]T(v)[/math] — поддеревья различных вершин дерева [math]T[/math], то либо они не пересекаются, либо [math]u[/math] — предок [math]v[/math], и значит [math]T(v) \subset T(u)[/math], либо [math]v[/math] — предок [math]u[/math], и значит [math]T(u) \subset T(v)[/math].
  5. Для доказательства последнего свойства в качестве вершины [math]c[/math] выберем [math]lca(u, v)[/math] в дереве центроидов [math]T[/math]. Покажем, что так выбранная вершина [math]c[/math] удовлетворяет заявленным свойствам. То, что [math]u, v \in T(c)[/math] — очевидно по определению [math]lca[/math], так как каждый предок любой вершины в дереве центроидов содержит эту вершину. Теперь докажем, что [math]c[/math] лежит на пути между парой вершин [math]u, v[/math]. Так как [math]c = lca(u, v)[/math] в [math]T[/math], то из [math]c[/math] нет ребра в такого сына, который содержит одновременно [math]u[/math] и [math]v[/math] в своем поддереве (в дереве [math]T)[/math], значит после удаления [math]c[/math] дерево [math]t[/math] разделится на несколько поддеревьев, таких что вершины [math]u[/math] и [math]v[/math] окажутся в разных компонентах связности. А значит найдется такое ребро [math](c, x)[/math], которое принадлежало пути из [math]u[/math] в [math]v[/math], но после удаления [math]c[/math] удалилось. Это доказывает то, что вершина [math]c[/math] лежала на пути из [math]u[/math] в [math]v[/math].
[math]\triangleleft[/math]

С помощью описанных свойств дерева [math]T[/math] мы можем решить задачу [math]2[/math] для дерева:

Пример решения задачи с помощью центроидной декомпозиции

Задача:
Есть дерево [math]t[/math] из [math]n[/math] вершин. В каждый момент времени любая вершина дерева может быть либо помечена, либо нет. Изначально помечена только вершина номер [math]0[/math]. Дан список из [math]m[/math] запросов:
  • Вершину [math]v[/math] пометили.
  • С вершины [math]v[/math] сняли пометку.
  • Найти номер ближайшей к [math]v[/math] помеченной вершины[2].


Решение

Построим центроидную декомпозицию [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] есть [math]len(u, v) = h(u) + h(v) - 2 \cdot h(lca(u, v))[/math]. Если изначально предпосчитать проходом [math]dfs[/math] величины [math]h(v)[/math] за [math]O(n)[/math], то ответ на запрос [math]len(u, v)[/math] можно делать за время [math]O(\log(n))[/math] с [math]O(n \cdot \log(n)) [/math]доп. памятью. Также можно воспользоваться техникой сведения задачи LCA к RMQ и решить с [math]O(n)[/math] дополнительной памятью и [math]O(1)[/math] времени на запрос. Теперь научимся отвечать на запросы. Из последнего свойства центроидной декомпозиции видно, что если [math]u[/math] — искомая ближайшая помеченная вершина к [math]v[/math], то путь между ними содержит центроид [math]c[/math], такой что [math]u, v \in T(c)[/math], причем [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]. Этот запрос занимает так же [math]O(log^2(n))[/math] времени.

Итак, мы научились решать задачу с [math]O(n)[/math] дополнительной памятью и временной сложностью [math]O(log^2(n))[/math] на запрос любого типа с предварительным предпосчетом за [math]O(n)[/math].

Варианты хранения центроидной декомпозиции

Для хранения дерева центроидов [math]T[/math] есть [math]2[/math] подхода, имеющих свои преимущества и недостатки:

  • Для каждой вершины [math]v[/math] исходного дерева запомним величину [math]p_v[/math] — номер предка вершины [math]v[/math] в дереве [math]T[/math].

Этот подход наиболее экономный по памяти [math](O(n))[/math], но уступает в скорости и функциональности.

  • Для каждой вершины [math]v[/math] исходного дерева будем хранить весь массив предков [math]p[v][/math] в дереве центроидов.

Этот подход уступает в количестве необходимой дополнительной памяти [math](O(n \cdot \log(n))[/math] суммарно), но имеет ряд преимуществ:

  1. При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, так как весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован
  2. На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков [math]O(log(\log(n)))[/math] на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за [math]O(\log(\log(n))[/math] на запрос, так как размер массива предков есть [math]O(\log(n))[/math] (по свойству [math]1[/math] центроидной декомпозиции). Используя эту оптимизацию можно получить время [math]O(\log(n)) + O(\log(\log(n)) = O(\log(n))[/math] на запрос нахождения ближайшей помеченной вершины. Чтобы добиться улучшенной асимптотики для запросов изменения можно хранить дерево отрезков на каждом из путей [math]p[v][/math], в каждой вершине которого хранить двоичное дерево поиска и поддерживать отложенные операции. Тогда ответ на эти запросы будет занимать [math]O(\log(n) \cdot \log(\log(n))[/math] времени.

См. также

Примечания

Источники информации