234
правки
Изменения
→Link-cut tree
Ключевая операция в link-cut-деревьях {{---}} <tex>expose(u)</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем представляемого дерева и при этом становится корнем в splay-дереве получившегося пути.
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
expose(u)
splay(u)
v <- u
while (v != root)
p <- pathparent(v) //получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня
splay(p) //теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,
parent(right(p)) <- null //поэтому правое поддерево p делаем новым путем
pathparent(right(p)) <- p
right(p) <- v //объеденяем оставшийся и построенный пути
Δw(v) -= Δw(p)
Δmin(p) = min{0, Δmin(left(p)) + Δw(left(p)), Δmin(right(p)) + Δw(right(p))}
pathparent(v) <- null
v <- p
splay(u)
===add(v, c)===
Чтобы прибавить константу на пути от <tex>v</tex> до корня link-cut-дерева вызовем <tex>expose(v)</tex>, что построит запрашиваемый путь в виде splay-дерева, в котором <tex>v</tex> - корень, и в левом поддереве находятся вершины, которые находятся выше чем <tex>v</tex> в link-cut-дереве (то есть все вершины пути без <tex>v</tex>), а в правом - те, что ниже. Тогда прибавим <tex>c</tex> к <tex>\Delta w(v)</tex> и вычтем константу от правого ребенка <tex>v</tex>, чтобы скомпенсировать разницу и сохранить инвариант.
