Изменения

Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>. Было бы хорошо, чтобы вершина не всплывала до корня; , и тогда дерево не придется сильно перестраивать. Для этого, при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:

При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (<tex> x.p.degree[p[x]] </tex>) и снимаем пометку с текущей вершины (<tex> x.mark[x] = false </tex>).