Изменения

Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель <tex>\mathrm{pathparent}</tex>.

Первый вызов <tex>\mathrm{expose}</tex> построит путь от <tex>u</tex> до корня. Второй пересечет этот путь в наименьшем общем предке, поэтому в splay-дереве, которому принадлежит <tex>u</tex>, хранится указатель <tex>\mathrm{pathparent}</tex> на <tex>\mathrm{lca}</tex>, после <tex>\mathrm{splay}(u)</tex> он будет находиться в <tex>u</tex>.