234
правки
Изменения
→Link-cut tree
==Link-cut tree==
Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в представляемом дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель <tex>pathparent</tex>.
[[Файл:Linkcut_paths.png|500px||center|Разбиение дерева на пути]]
