234
правки
Изменения
→link(v, w)
Ключевая операция в link-cut-деревьях {{---}} <tex>expose(u)</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем представляемого дерева и при этом становится корнем в splay-дереве получившегося пути.
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
===link(v, wu)===Если <tex>v</tex> - корень, а <tex>u</tex> - вершина в другом дереве, то <tex>link(v, u)</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>u</tex> становится родителем <tex>v</tex>. link(v, u) expose(v) //теперь v - корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в представляемом дереве) expose(u) Δw(u) -= Δw(v) //чтобы сделать u родителем v в представляемом дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве parent(u) = v // 2. обновляем Δw, Δmin left(v) = u Δmin(v) = min{0, Δmin(u) + Δw(u), Δmin(right(v)) + Δw((right(v)))}
