Привет всем. Наверное каждый зарегистрированный на CodeForces хоть раз слышал о таком замечательном сайте, как e-maxx. Там можно получить довольно подробную информацию по алгоритмам и реализацию на C++ — для копипаста (что не совсем хорошо) или усвоения особенностей реализации алгоритма в неидеальном реальном мире.
Алгоритмов то много, но вот про Link-Cut Tree ничего небыло, а это очень интересная структура и довольно простая. На самом деле, разобраться с ней было не так то и просто с первой попытки, но со второй все стало на свои места. После этого захотелось посмотреть на примеры реализации, выбрать лучшие решения и реализовать самостоятельно. Но вот с примерами возникли проблемы — я не смог найти внятной реализации (может быть плохо искал?). После десятка переписываний кода и долгого дебага я получил довольно внятную структуру данных, которую можно использовать как замену HLD.
Я поддержал следующие операции (все работают за $$$O(\log n)$$$ амортизировано):
Unable to parse markup [type=CF_MATHJAX]
— соединить вершину $$$x$$$ с вершиной $$$y$$$ (в случае, если вершина x не является корнем, дерево будет переподвешено).Unable to parse markup [type=CF_MATHJAX]
— удалить ребро от вершины $$$x$$$ до родителя.Unable to parse markup [type=CF_MATHJAX]
— переподвесить дерево за вершину $$$x$$$.Unable to parse markup [type=CF_MATHJAX]
— найти расстояние между вершинами.Unable to parse markup [type=CF_MATHJAX]
— найти глубину вершины $$$x$$$.$$$lca(x, y)$$$ — найти LCA вершин $$$x$$$ и $$$y$$$.
Unable to parse markup [type=CF_MATHJAX]
— найти родителя вершины $$$x$$$.Unable to parse markup [type=CF_MATHJAX]
— найти корень дерева, где находится вершина x.$$$path(x, y)$$$ — проверить наличие пути между вершинами x и y.
Unable to parse markup [type=CF_MATHJAX]
— посчитать сумму значений в вершинах на пути от $$$x$$$ до $$$y$$$.Unable to parse markup [type=CF_MATHJAX]
— прибавить $$$v$$$ к каждой вершине на пути от $$$x$$$ до $$$y$$$.Исходный код здесь.
На данный момент не гарантирую, что в данной реализации нет багов, если кто и найдет, то пожалуйста расскажите, как они воспроизводятся.