186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
Кратчайший путь из любой вершины <math>v</math> до любой помеченной вершины в дереве <math>t</math> проходит через какой-то центроид <math>с \in T(t)</math>, такой что <math>c</math> содержит обе вершины (вершину <math>v</math> и ближайшую к ней помеченную).
|proof=
Предположим, что вершина <math>u</math> - ближайшая к <math>v</math> среди помеченных. Тогда кратчайший путь между <math>u</math> и <math>v</math> состоит из двух промежутков - пути <math>v -~> lca(u, v)</math> и пути <math>lca(u, v) -~> u</math>.
}}
