186
правок
Изменения
→Статическая центроидная декомпозиция
|id=191213
|definition =
'''Центроидом дерева''' (англ. ''centroid'') называется такая вершина <math>v</math> дерева <math>t</math>, после удаления которой дерево разбивается на несколько (<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>, после чего попытаемся найти недостающие пары вершин, находящиехя в разных поддеревьях и удовлетворяющих вопросу задачи.
