186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
* Каждая вершина дерева <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> верно ровно одно из следующих трех утверждений :
a) <tex>T(v) \subset T(u)<\/tex>b) <tex>T(u) \subset T(v)<\/tex>c) <tex>T(u) \cap T(v) = \emptyset <\/tex>
|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>, ч.т.д.
