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> по сумме весов.
}}
Для решения новой задачи применим ту же идею, что и была до этого - разделяй и властвуй. Для этого нам потребуется следующий объект : {{Определение|id=191213|definition ='''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева t, после удаления которой дерево разбивается на несколько (<math>k</math>) поддеревьев <tex>t_1, t_2,..., t_k</tex>, таких что <tex>/all i (0 < i < k + 1) : |t_i| <= \frac{n}{2}</tex>.}} Но в случае дерева эта идея будет формулироваться так : разделим дерево на несколько поддеревьев <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>, после чего попытаемся найти недостающие пары вершин, находящиехя в разных поддеревьях и удовлетворяющих вопросу задачи.
=== Лемма о центроиде ===
