Изменения

Перейти к: навигация, поиск

Centroid decomposition

2 байта убрано, 16:17, 14 июня 2017
м
Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
Кратчайший путь из любой вершины <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>.
}}
186
правок

Навигация