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

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

Я поддержал следующие операции (все работают за $$$O(\log n)$$$ амортизировано):

$$$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$$$.

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

На данный момент не гарантирую, что в данной реализации нет багов, если кто и найдет, то пожалуйста расскажите, как они воспроизводятся.

Хочется услышать критику со стороны сообщества (и о том, что я плохо искал или написал плохой код).