234
правки
Изменения
→add(v, c)
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
===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>, чтобы скомпенсировать разницу и сохранить инвариант.
add(v, c)
expose(v)
Δw(v) += c
Δw(right(v)) -= c
===link(v, u)===
Если <tex>v</tex> - корень, а <tex>u</tex> - вершина в другом дереве, то <tex>link(v, u)</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>u</tex> становится родителем <tex>v</tex>.
