Изменения

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

Link-Cut Tree

62 байта добавлено, 22:50, 10 июня 2014
Решение задачи в частном случае
* подвешивать голову одного пути к хвосту другого.
Если бы не последние две операции, то можно было бы применить [[Дерево отрезковНесогласованные поддеревья. ПостроениеРеализация массового обновления|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Если использовать какие-нибудь сливаемые деревья, то <tex>\mathrm{link}</tex> и <tex> \mathrm{cut}</tex> реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах.
В качестве сливаемых деревьев выберем [[Splay-дерево|splay-деревья]], в которых ключи выбираются равными глубине вершины.
234
правки

Навигация