Изменения
→Статическая центроидная декомпозиция
Перейдем к обобщению поставленных задач на случай дерева. Начнем, как и полагается, с первой:
{{Задача
|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>)
}}
Для решения новой задачи применим ту же идею, что и была до этого {{---}} разделяй и властвуй. Для этого нам потребуется следующий объект:
