Изменения

C помощью link-cut-дерева можно найти наименьшего общего предка:

'''lca(u, v)

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

==Ссылки==

*[http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf ''D. Sleator and R. Tarjan''. A Data Structure for Dynamic Trees]