234
правки
Изменения
→Link-cut tree
==Link-cut tree==
Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в представляемом link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель <tex>pathparent</tex>.
[[Файл:Linkcut_paths.png|500px||center|Разбиение дерева на пути]]
===expose(u)===
Ключевая операция в link-cut-деревьях {{---}} <tex>expose(u)</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем представляемого link-cut дерева и при этом становится корнем в splay-дереве получившегося пути.
[[Файл:Linkcut_expose.png|500px||center|Разбиение дерева на пути]]
'''expose(u)'''
splay(u)
v <- u
while (v != root)
p <- pathparent(v) <font color=green>//получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня</font> splay(p) <font color=green>//теперь в правом поддереве p находятся вершины пути, которые находятся ниже чем p в link-cut-дереве,</font> parent(right(p)) <- null <font color=green>//поэтому правое поддерево p делаем новым путем</font>
pathparent(right(p)) <- p
right(p) <- v <font color=green>//объединяем оставшийся и построенный пути</font>
Δw(v) -= Δw(p)
Δmin(p) = min{0, Δmin(left(p)) + Δw(left(p)), Δmin(right(p)) + Δw(right(p))}
