Изменения

Ключевая операция в link-cut-деревьях {{---}} <tex>expose(u)</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем представляемого дерева и при этом становится корнем в splay-дереве получившегося пути.

[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]

===link(v, u)===

Если <tex>v</tex> - корень, а <tex>u</tex> - вершина в другом дереве, то <tex>link(v, u)</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>u</tex> становится родителем <tex>v</tex>.

left(v) = u

Δmin(v) = min{0, Δmin(u) + Δw(u), Δmin(right(v)) + Δw((right(v)))}

===cut(v)===

Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>expose(v)</tex> <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже <tex>v</tex> в представляемом дереве, а в левом - те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.