Link-Cut Tree

Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции:

• искать минимум на пути от вершины до корня;
• прибавлять константу на пути от вершины до корня;
• link(u,w) -- подвешивать одно дерево на другое;
• cut(v) -- отрезать дерево с корнем в вершине v.

Решение задачи в частном случае

Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм ключи выбираются равными глубине вершины.