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]v[/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] и минимум её левого ребенка.