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