188
правок
Изменения
Нет описания правки
Задача, которая решается с помощью [[Link-Cut Tree|динамических деревьев]], формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* <tex>\mathrm{link(u, v)}</tex> {{---}} добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,* <tex>\mathrm{cut(u, v)}</tex> {{---}} удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,* <tex>\mathrm{query}</tex> {{---}} некоторый запрос относительно структуры дерева.
