Изменения
→Идея
Пусть каждое дерево поддерживает следующие операции:
# Вычислить минимум на пути от вершины до корня(1).# Прибавить константу к числам на пути от вершины до корня(2).# Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева(3).# Подвесить дерево. Пусть есть дерево с корнем <tex>A</tex>, дерево с вершиной <tex>B</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex> и тем самым подвесить дерево к вершине(4).
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|Link-Cut tree]] и умеет их выполнять за <tex>O(\log(N))</tex>.
