Link Cut

• link(u, v) - u становится сыном v, причем u корень.
• cut(u, v) - отрезать ребро.
• change(v, x) - поменять на вершине значение на x.
• min(u, v) - минимум на пути из u в v

Как все будет работать?

Некоторые ребра выделенные. У каждой вершины не более одного выделенного ребра в сына.

Введем операцию expose(v): Выделить все ребра от v до корня. И давайте для каждого выделенного пути хранить splay дерево.

Как только научимся делать данную операцию, покажем как через нее поулчить другие:

Изначально все веришны одиночные и в каждой веришне свое splay дерево

expose

void expose(v){
    splay(v);
    while(v != root){
        u = v.parenth;
        splay(u);
        r = u.right;
        r.pathparent = u;
        отрезать поддерево r;
        u.right = v;
        v.pathparenth = null;
        v =u; 
    }   
}

То есть поднмаемся сверух вниз, отрезаем splay дерево, если надо, иначе поднимаемся выше и соединяем нужные splay

Использование expose для операций

• link(u, v) — делаем expose(u), expose(v), затем присоединяем (u) к (v) как ребёнка.
• cut(u) — делаем expose(u), отрезаем ребро между (u) и его родителем.
• change(v, x) — делаем expose(v), обновляем значение в вершине (v) (корне splay-дерева).
• min(u, v) — делаем expose(u), затем expose(v), теперь путь (u \to v) представлен в splay-дереве, на котором можно за (O(\log n)) получить минимум.

Важные моменты

• Каждый splay-узел хранит агрегированную информацию о поддереве (например, минимум).
• При splay-поворотах агрегаты обновляются.
• pathparent — ссылка на родителя вне splay-дерева (в исходном дереве).
• Вся работа со структурами происходит через splay-операции.