Изменения

Перейти к: навигация, поиск

Link-Cut Tree

69 байт добавлено, 23:29, 1 апреля 2016
Решение задачи в частном случае
* '''<tex>\mathrm{link(v, u)}</tex>''' {{---}} подвешивать голову одного пути к хвосту другого.
Если бы не последние две операции, то можно было бы применить [[Несогласованные поддеревья. Реализация массового обновления|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Эту задачу можно решить при помощи [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]]. Также, если использовать какие-нибудь сливаемые деревья, то <tex>\mathrm{link}</tex> и <tex> \mathrm{cut}</tex> реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах.
В качестве сливаемых деревьев выберем [[Splay-дерево|splay-деревья]], в которых ключи выбираются равными глубине вершины.
Анонимный участник

Навигация