234
правки
Изменения
→Решение задачи в частном случае
==Решение задачи в частном случае==
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.[[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]
Тогда операциям link и cut будут соответсвовать merge и split.
сумма
Для поиска минимума поступим аналогично. Определим <tex>\Delta min(v)</tex> таким образом, чтобы сохранялся следующий инвариант: <tex>min(v) = \Delta min(v) + w(v) </tex>. Пусть <tex>l</tex> и <tex>r</tex> дети <tex>v</tex>, тогда
Чтобы найти минимум на пути, надо вызвать <tex>splay(v)</tex>, а затем сравнить минимум <tex>v</tex> и минимум её левого ребенка.
==Link-cut tree==
Чтобы обобщить, разобъем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в представляемом дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя.
[[Файл:Linkcut_paths.png|500px||center|Разбиение дерева на пути]]
Ключевая операция в link-cut-деревьях {{---}} <tex>expose(u)</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем представляемого дерева и при этом становится корнем в splay-дереве получившегося пути.
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
