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)$). Доказательство времени работы приводиться не будет.
Правила хранения
Будем хранить лес таким образом, чтобы после каждого запроса он удовлетворял следующим правилам:
- в каждом дереве есть корень;
- каждое дерево разбито на множество вертикальных путей, и каждый вертикальный путь (под путём понимается набор вершин, не рёбер) хранится в splay-дереве по неявному ключу;
- каждая вершина будет находиться ровно в одном splay-дереве;
- в каждом splay-дереве для каждой вершины $v$ выполняется следующее правило: если $l$ - левый ребёнок $v$, то любая вершина в поддереве $l$ находится ближе к корню дерева, чем $v$; если $r$ - правый ребенок $v$, то наоборот;
- если 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