234
правки
Изменения
Нет описания правки
'''Link-cut tree''' (''dinamic-tree'') {{---}} это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:
* '''min(v)''' {{- --}} искать минимум на пути от вершины до корня;* '''add(v, c)''' {{--- }} прибавлять константу на пути от вершины до корня;* '''link(u, w)''' {{--- }} подвешивать одно дерево на другое;* '''cut(v)''' {{--- }} отрезать дерево с корнем в вершине v.
Среднее время выполнения каждой операции - <tex>O(log(n))</tex>. Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году.
