Привет всем. Наверное каждый зарегистрированный на CodeForces хоть раз слышал о таком замечательном сайте, как e-maxx. Там можно получить довольно подробную информацию по алгоритмам и реализацию на C++, для копипаста (что не совсем хорошо) или усвоения особенностей реализации алгоритма в неидеальном реальном мире. Алгоритмов много, но вот про Link-Cut Tree ничего небыло, а это очень интересная структура и довольно простая. На самом деле, разобраться с ней было не так то и просто с первой попытки, но со второй все стало на свои места. После этого захотелось посмотреть на примеры реализации, выбрать лучшие решения и реализовать самостоятельно. Но вот с примерами возникли проблемы — я не смог найти внятной реализации (может быть плохо искал?). После десятка переписываний кода и долгого дебага я получил довольно внятную структуру данных, которую можно использовать как замену HLD.

Я поддержал следующие операции:

link(x, y) — соединить вершину x с вершиной y (в случае, если вершина x не является корнем, дерево будет переподвешено).

cut(x) — удалить ребро от вершины x до родителя.

evert(x) — переподвесить дерево за вершину x.

distance(x, y) — найти расстояние между вершинами.

depth(x) — найти глубину вершины x.

lca(x, y) — найти LCA вершин x и y.

parent(x) — найти родителя вершины x.

root(x) — найти корень дерева, где находится вершина x.

path(x, y) — проверить наличие пути между вершинами x и y.

query(x, y) — посчитать сумму значений в вершинах на пути от x до y.

update(x, y, v) — прибавить v к каждой вершине на пути от x до y.

Исходный код здесь.