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