Link-Cut Tree

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

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

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

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

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

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

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

сумма

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

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

[math]min(v) = min\{w(v), min(l), min(r)\}[/math]

[math]\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)\}[/math]

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

Link-cut tree

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

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