234
правки
Изменения
Нет описания правки
* '''link(u, w)''' {{---}} подвешивать одно дерево на другое;
* '''cut(v)''' {{---}} отрезать дерево с корнем в вершине v.
Среднее время выполнения каждой операции {{- --}} <tex>O(\log n)</tex>. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.
==Решение задачи в частном случае==
===add(v, c)===
Чтобы прибавить константу на пути от <tex>v</tex> до корня link-cut-дерева вызовем <tex>\mathrm{expose(v)}</tex>, что построит запрашиваемый путь в виде splay-дерева, в котором <tex>v</tex> {{- --}} корень, и в левом поддереве находятся вершины, которые находятся выше чем <tex>v</tex> в link-cut-дереве (то есть все вершины пути без <tex>v</tex>), а в правом {{--- }} те, что ниже. Тогда прибавим <tex>c</tex> к <tex>\Delta w(v)</tex> и вычтем константу от правого ребенка <tex>v</tex>, чтобы скомпенсировать разницу и сохранить инвариант.
'''function''' add(v : '''tree''', c : '''int'''):
===link(v, u)===
Если <tex>v</tex> {{- --}} корень, а <tex>u</tex> {{--- }} вершина в другом дереве, то <tex>\mathrm{link(v, u)}</tex> соединяет два дерева добавлением ребра <tex>(v, u)</tex>, причем <tex>u</tex> становится родителем <tex>v</tex>.
'''tree''' link(v : '''tree''', u : '''tree'''):
expose(v) <font color=green> //теперь v {{- --}} корень в splay-дереве пути и не имеет левого ребенка(так как ключ равен глубине в link-cut дереве)</font>
expose(u)
<tex>\vartriangle</tex>w(u) -= <tex>\vartriangle</tex>w(v) <font color=green>//чтобы сделать u родителем v в link-cut дереве 1. делаем путь, содержащий u, левым ребенком v в splay-дереве</font>
===cut(v)===
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>\mathrm{expose(v)}</tex> вершина <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом {{- --}} те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
'''function''' cut(v : '''tree'''):
}}
Операция <tex>u</tex> осуществляется с помощью последовательности преобразований dashed-ребра в solid-ребро и другого solid-ребра в dashed-ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{--- }} множество всех тяжелых ребер, <tex>L</tex> {{--- }} все легкие ребра, <tex>S \rightarrow D</tex> {{--- }} множество solid-ребер, преобразованных в dashed в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{--- }} множество dashed-ребер, преобразованных в solid.
<tex>M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|</tex>
