Link-Cut Tree
Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:
- искать минимум на пути от вершины до корня;
- прибавлять константу на пути от вершины до корня;
- link(u,w) -- подвешивать одно дерево на другое;
- cut(v) -- отрезать дерево с корнем в вершине v.
Содержание
Решение задачи в частном случае
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.Тогда операциям link и cut будут соответсвовать merge и split.
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить велечину
, которая равна разнице между весом вершины и весом её ролителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:сумма
При прибавлении
на пути от вершины до корня, сначала вызвается , после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить к и ,чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть от .Для поиска минимума поступим аналогично. Определим
таким образом, чтобы сохранялся следующий инвариант: . Пусть и дети , тогда
Чтобы найти минимум на пути, надо вызвать
, а затем сравнить минимум и минимум её левого ребенка.
Link-cut tree
Чтобы обобщить, разобъем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в представляемом дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя.
Ключевая операция в link-cut-деревьях —
. После её выполнения лежит на одном пути с корнем представляемого дерева и при этом становится корнем в splay-дереве получившегося пути.add(v, c)
Чтобы прибавить константу на пути от
до корня link-cut-дерева вызовем , что построит запрашиваемый путь в виде splay-дерева, в котором - корень, и в левом поддереве находятся вершины, которые находятся выше чем в link-cut-дереве (то есть все вершины пути без ), а в правом - те, что ниже. Тогда прибавим к и вычтем константу от правого ребенка , чтобы скомпенсировать разницу и сохранить инвариант.add(v, c) expose(v) Δw(v) += c Δw(right(v)) -= c
min(v)
link(v, u)
Если
- корень, а - вершина в другом дереве, то соединяет два дерева добавлением ребра , причем становится родителем .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)
Отрезает дерево с корнем
. После вызова станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже в представляемом дереве, а в левом - те что выше. Обнулив указатель на левого ребенка и на родителя в левом поддереве, получим требуемое.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