234
правки
Изменения
Новая страница: «Link-cut tree {{---}} это структура данных, которая хранит лес деревьев и позволяет выполнять сле...»
Link-cut tree {{---}} это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:
* искать минимум на пути от вершины до корня;
* прибавлять константу на пути от вершины до корня;
* link(u,w) -- подвешивать одно дерево на другое;
* cut(v) -- отрезать дерево с корнем в вершине v.
==Решение задачи в частном случае==
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.
* искать минимум на пути от вершины до корня;
* прибавлять константу на пути от вершины до корня;
* link(u,w) -- подвешивать одно дерево на другое;
* cut(v) -- отрезать дерево с корнем в вершине v.
==Решение задачи в частном случае==
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.
