Link-cut tree

Link-cut tree

Постановка задачи

Пусть нам дан набор из $n$ вершин. Поступают запросы:

• link(u, v) - провести ребро между вершинами $u$ и $v$.
• cut(u, v) - удалить ребро между вершинами $u$ и $v$.
• любые запросы на путях, на которые мы умеем отвечать с помощью Heavy-Light декомпозиции.

Гарантируется, что после каждого добавления ребра граф будет лесом.

Отвечать на запросы мы будем в онлайне в среднем за $O(log n)$ (при использовании в реализации splay-деревьев; если использовать другие деревья двоичного поиска по неявному ключу, среднее время операции будет составлять $O(log^2 n)$). Доказательство времени работы приводиться не будет.

Правила хранения

Будем хранить лес таким образом, чтобы после каждого запроса он удовлетворял следующим правилам:

1. в каждом дереве есть корень;
2. каждое дерево разбито на множество вертикальных путей, и каждый вертикальный путь (под путём понимается набор вершин, не рёбер) хранится в splay-дереве по неявному ключу;
3. каждая вершина будет находиться ровно в одном splay-дереве;
4. в каждом splay-дереве для каждой вершины $v$ выполняется следующее правило: если $l$ - левый ребёнок $v$, то любая вершина в поддереве $l$ находится ближе к корню дерева, чем $v$; если $r$ - правый ребенок $v$, то наоборот;
5. если splay-дерево не содержит корень дерева, то в корне splay-дерева (то есть в вершине, у которой нет предка) хранится ссылка на предка самой близкой к корню вершины внутри splay-дерева; все остальные вершины не содержат ссылок.

Две главные операции

 1 struct node {
 2   int x; // номер вершины в лесе
 3   int sz; // размер поддерева в splay-дереве
 4   bool rev; // отложенная операция разворота поддерева
 5   // pathparent - ссылка, о которой шла речь в правиле 5
 6   node *left, *right, *parent, *pathparent;
 7   node(int _x) {
 8     x = _x;
 9     sz = 1;
10     rev = false;
11     left = right = parent = pathparent = nullptr;
12   }
13   ...
14 };

expose(v)

Функция expose будет прокладывать путь от $v$ до корня дерева, в котором находится $v$ (то есть будет перестраивать лес splay-деревьев так, что $v$ и корень окажутся в одном splay-дереве). В среднем expose будет работать за $O(log n)$.

 1 static void splay(node* v) {
 2   while(v->parent) {
 3     // пока мы поднимаем вершину в корень, мы хотим не забыть
 4     // поддерживать выполнение правила 5
 5     if (есть ссылка из отца)
 6       swap(v->parent->pathparent, v->pathparent);
 7     if (есть дед и есть ссылка из него)
 8       swap(v->parent->parent->pathparent, v->pathparent);
 9     ...
10     // затем тот же код, что и в обычном splay
11   }
12 }
13 
14 static void expose(node* v) {
15   splay(v);
16   while (v->pathparent) {
17     // хотим, чтобы v и v->pathparent оказались в одном splay-дереве
18     node* p = v->pathparent;
19     splay(p); // подняли p в корень splay-дерева
20     // заметим, что в правом поддереве p находятся все
21     // вершины, которые дальше от корня, чем p
22     if (p->right) // разбиваем путь на два
23       swap(p->right->parent, p->right->pathparent);
24     p->right = v;
25     v->parent = p;
26     v->pathparent = nullptr;
27     upd(p);
28     splay(v);
29   }
30 }

make_root(v)

 1 static void make_root(node* v) {
 2   expose(v);
 3   if (v->right) {
 4     v->right->pathparent = v;
 5     v->right->parent = nullptr;
 6     v->right = nullptr;
 7     upd(v);
 8   }
 9   v->rev ^= 1;
10 }

Утверждение:
make_root(v) делает $v$ корнем дерева (и все правила, по которым мы храним пути, выполняются).

Доказательство остаётся читателю в качестве упражнения

Все остальные функции

 1 static void link(node* u, node* v) {
 2   make_root(u);
 3   u->pathparent = v;
 4 }
 5 
 6 static void cut(node* u, node* v) {
 7   make_root(u);
 8   expose(v);
 9   // убедитесь, что теперь v->left->sz = 1 и v->left = u
10   v->left->parent = nullptr;
11   v->left = nullptr;
12 }

Если по какой-то причине важно оставлять корни деревьев прежними, то просто перед каждым вызовом make_root(v) будем запоминать корень дерева, делать что-нибудь, а затем переподвешивать дерево обратно за корень.

Функции на путях

Если запросы выглядят как "в вершинах хранятся числа, вывести результат на пути", то надо будет лишь добавить пару строк в upd и push (в вершине $v$ splay-дерева будем поддерживать результат для пути на вершинах, находящихся в поддереве $v$).

 1 static int get(node* u, node* v) {
 2   if (u и v в разных деревьях)
 3     return -1; // если по условию такого не бывает, во время дебага сюда можно что-нибудь добавить
 4   make_root(u);
 5   expose(v);
 6   if (v->right) { // такое мы уже писали, имеет смысл написать функцию "вырежи_правого_сына" отдельно
 7     v->right->pathparent = v;
 8     v->right->parent = nullptr;
 9     v->right = nullptr;
10     upd(v);
11   }
12   return v->func;
13 }

Если запросы на рёбрах, то вместо добавления ребра ($u$, $v$) будем добавлять фиктивную вершину $w$, в которой будем хранить результат на ребре, и ребра ($u$, $w$), ($w$, $v$) (в $u$ и $v$ будем хранить нейтральные элементы).

---

Автор конспекта: Герман Перов

По всем вопросам пишите в telegram @gmusya