Link-Cut Tree

Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:

• искать минимум на пути от вершины до корня;
• прибавлять константу на пути от вершины до корня;
• link(u,w) -- подвешивать одно дерево на другое;
• cut(v) -- отрезать дерево с корнем в вершине v.

Решение задачи в частном случае

Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.

Пример построения дерева для пути

Тогда операциям link и cut будут соответсвовать merge и split.

Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить велечину $\Delta w$, которая равна разнице между весом вершины и весом её ролителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:

сумма

При прибавлении $\alpha$ на пути от вершины $v$ до корня, сначала вызвается $splay(v)$, после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить $\alpha$ к $\Delta w(v)$ и ,чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть $\alpha$ от $\Delta w(v.right)$.

Для поиска минимума поступим аналогично. Определим $\Delta min(v)$ таким образом, чтобы сохранялся следующий инвариант: $min(v) = \Delta min(v) + w(v)$. Пусть $l$ и $r$ дети $v$, тогда

$min(v) = min\{w(v), min(l), min(r)\}$

$\Delta min(v) = min(v) - w(v) \\ = min\{w(v) - w(v), min(l) - w(v), min(r) - w(v)\} \\ = min\{0, (\Delta min(l) + w(l)) - w(v), (\Delta min(r) + w(r)) - w(v)\} \\ = min\{0, \Delta min(l) + \Delta w(l), \Delta min(r) + \Delta w(r)\}$

Чтобы найти минимум на пути, надо вызвать $splay(v)$, а затем сравнить минимум $v$ и минимум её левого ребенка.

Link-cut tree

Чтобы обобщить, разобъем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в представляемом дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя.

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

add(v, c)

Чтобы прибавить константу на пути от $v$ до корня link-cut-дерева вызовем $expose(v)$, что построит запрашиваемый путь в виде splay-дерева, в котором $v$ - корень, и в левом поддереве находятся вершины, которые находятся выше чем $v$ в link-cut-дереве (то есть все вершины пути без $v$), а в правом - те, что ниже. Тогда прибавим $c$ к $\Delta w(v)$ и вычтем константу от правого ребенка $v$, чтобы скомпенсировать разницу и сохранить инвариант.

add(v, c)
    expose(v)
    Δw(v) += c
    Δw(right(v)) -= c

link(v, u)

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

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)))}

cut(v)

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

cut(v)
    expose(v)
    Δw(left(v)) += Δw(v)
    Δmin(v) = min{0, Δmin(right(v)) + Δw(right(v))}
    left(v) = null
    parent(left(v)) = null