186
правок
Изменения
→Статическая центроидная декомпозиция
|definition = Есть взвешенное дерево <tex>t</tex> из <tex>n</tex> вершин, в каждой вершине которого написаны положительные целые числа. Также по-прежнему даны числа <tex>W >= 0</tex> и <tex>l</tex>. Требуется найти количество пар <tex>(i, j)</tex> вершин дерева, таких что расстояние между ними не превосходит <math>l</math> по числу ребер и не превосходит <math>W</math> по сумме весов.
}}
Для решения новой задачи применим ту же идею, что и была до этого - разделяй и властвуй. Но в случае дерева эта идея будет формулироваться так : разделим дерево на несколько поддеревьев <tex>t_1, t_2,..., t_k</tex> одной из вершин (<math>v</math>), таких что каждое из них имеет размер, не превосходящий <math> \frac{n}{2}</math>. Такая вершина <math>v</math> будет называться центроидом дерева (доказательство её существования и алгоритм нахождение см. далее). Предположим, что мы сумели найти центроид за <math>O(n)</math>, где <math>n</math> - размер дерева. Тогда, как и в упрощенной версии задачи - рекурсивно найдем ответ для всех поддеревьев <tex>t_1, t_2,..., t_k</tex>, после чего попытаемся найти недостающие пары вершин, находящиехя в разных поддеревьях и удовлетворяющих вопросу задачи.
=== Лемма о центроиде ===
=== Алгоритм нахождения центроида в произвольном дереве ===
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
