Реализация Link-Cut Tree

Revision ru4, by wilcot, 2019-09-19 01:00:14

Привет всем. Наверное каждый зарегистрированный на 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$$$.

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

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

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

Tags link-cut-tree, lca, hld

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru8 Russian wilcot 2019-09-19 01:11:36 2 Мелкая правка: ' вершину $x$:\n\n$que' -> ' вершину $y$:\n\n$que'
ru7 Russian wilcot 2019-09-19 01:10:24 84
ru6 Russian wilcot 2019-09-19 01:08:26 179
ru5 Russian wilcot 2019-09-19 01:00:55 0 (опубликовано)
ru4 Russian wilcot 2019-09-19 01:00:14 103
ru3 Russian wilcot 2019-09-19 00:59:10 24
ru2 Russian wilcot 2019-09-19 00:57:28 226 Мелкая правка: 'ают за $O(log n)$):\' -> 'ают за $O(\log n)$):\'
ru1 Russian wilcot 2019-09-19 00:52:09 1777 Первая редакция (сохранено в черновиках)