234
правки
Изменения
Нет описания правки
==Решение задачи в частном случае==
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.
[[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]
Тогда операциям link и cut будут соответсвовать merge и split.
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить велечину <tex>\Delta w</tex>, которая равна разнице между весом вершины и весом её ролителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:
сумма
Чтобы прибавить <tex>\alpha</tex> на пути от вершины <tex>v</tex> до корня, надо вызвать <tex>splay(v)</tex>, прибавить <tex>\alpha</tex> к <tex>\Delta w(v)</tex> и вычесть <tex>\alpha</tex> от <tex>\Delta w(v.right)</tex>, чтобы сохранить веса вершин которые находятся ниже <tex>v</tex> в пути.
[[Файл:Linkcut_weights.png|250px|thumb|right|Представление веса вершины]]
Для поиска минимума поступим аналогично. Определим <tex>\Delta min(v)</tex> таким образом, чтобы сохранялся следующий инвариант: <tex>min(v) = \Delta min(v) + w(v) </tex>. Пусть <tex>l</tex> и <tex>r</tex> дети <tex>v</tex>, тогда
<tex>min(v) = min\{w(v), min(l), min(r)\}</tex>
<tex>\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)\}</tex>
