LCT 学习笔记，防忘

动态树

有一类问题，要求我们维护树上路径的信息，如果树是静态的，即树的结构是不会变的，树链剖分可以解决这类问题。但是如果要求支持我们修改树的结构，比如加边，删边等操作，树剖就 gg 了。。

这种动态维护树上信息的问题，我们称之为动态树问题，上述例子是比较简单的动态树问题，不存在对子树进行操作等丧心病狂的操作，所以我们可以用 Link-Cut Tree 来解决。

Link-Cut Tree

Link-Cut Tree 是一种能在 O(logn) O(\log n) 的时间内解决上述问题的数据结构。

简单来说， LCT 与树链剖分一样，会对树中节点的儿子进行划分，轻重链剖分根据子树大小将节点的儿子分为轻儿子和重儿子， LCT 则会将儿子划分为实、虚两种儿子，相应的边被称为实边和虚边，而且任意时刻，一个节点最多会有一个实儿子，也可能没有。

与树剖不同的是， LCT 并不固定划分实虚儿子，由于树的形态不断改变，实虚儿子也有可能变化。

基本定义

深度：深度越大，到根节点越远，反之亦然。

实边：一个非叶节点，向它的实儿子连的一条边叫做实边，向其他所有儿子连的边均为虚边。注意，一个非叶节点可以没有实儿子，此时它向所有儿子连边均为虚边。

实路径：由若干条实边首尾相连的，不可伸长的路径称之为实路径。实路径之间并非孤立的，各条实路径之间通过虚边连接。一条实路径中深度最小的点在树中的父节点被称之为实路径的父亲，在代码中用 pathFa 体现。

基本操作

用 Splay 来维护实路径。由于实路径中的任意两个节点都是祖先和子孙的关系，则如果我们按照节点的深度进行排序，我们会得到一个唯一的有序深度序列，换言之，在某条实路径对应的 Splay 中，一个节点的左子树中的所有节点一定是其祖先，右子树中的所有子树一定是其子孙，这也是我们用Splay维护实路径的原因。

在实际维护中，并不需要真的在 Splay 中用维护有序集的方法去排序，我们只需要在修改 Splay 的时候满足其中序遍历满足我们的需求即可。

我们设 v 是树中某个节点，v.OPERATION可以使得这个节点进行OPERATION这个操作。

  1. v.access 使得节点 v 到根节点的路径成为实路径。

    节点 v v 可能不是目前属实路径的尾部，所以我们将其旋转到其所属Splay的根节点，此时如果它有右子树，则它右子树中所有的节点都是它目前所处实路径的下方的节点，我们要断掉这条边（注意不是真的断掉，只是转换成虚边），要做的操作是将其右儿子的 pathFa 设成它，同时将其右儿子置空。

    如果此时这条实路径包含根节点，操作结束

    然后我们要做的是将以节点v为尾部的这条实路径和它的父亲相连，此时我们对这条实路径的父亲执行上述操作，并且将这条实路径的父亲向实路径的顶部节点的边置为实边，即在这条实路径对应的 Splay 中将原来的 pathFa 设为 fa 即可。

    继续查询该实路径是否包含根节点，若不包含，则继续执行上述操作。

  2. v.find 找到节点v所处这棵树的根节点。
    我们只需要执行v.access，此时节点v与根节点处在一条实路径中，而且根节点一定是深度最小的那个节点，所以查找实路径对应Splay的最左节点即可。

  3. v.evert 将节点v置为整棵树的根
    首先我们将节点v和根置于一条实路径上，即执行v.access，此时我们只需让这条实路径反转即可将v置为整棵树的根。利用平衡树打标记处理即可。 注：维护根不变的树时，不需要此操作。

  4. link(u, v) 将节点u和节点v连起来
    首先u.evert，然后将u所在实路径上的pathFa置成v即可。 注：这样操作，让节点u成为了节点v的儿子

  5. cut(u, v) 删掉节点u和节点v之间的边 先u.evert使得u成为有根树的根节点，这样保证v一定是节点u的子节点，然后v.access，再将v旋转至Splay的根，这样如果原树中有边(u, v)，那么v的左子树一定只有u这个节点。

附上「BZOJ2049」洞穴勘探 的代码

#include <cstdio>
#include <algorithm>
const int MAXN = 10000;
struct LinkCutTree {
    struct Node {
        Node *fa, *ch[2], *pathFa;
        bool rev;
        void pushDown() {
            if (rev) {
                std::swap(ch[0], ch[1]);
                if (ch[0]) ch[0]->rev ^= 1;
                if (ch[1]) ch[1]->rev ^= 1;
                rev = false;
            }
        }
        int relation() {
            return this == fa->ch[1];
        }
        void rotate() {
            pushDown();
            std::swap(pathFa, fa->pathFa);
            Node *old = fa;
            int x = relation();
            fa = old->fa;
            if (old->fa) old->fa->ch[old->relation()] = this;
            old->ch[x] = ch[x ^ 1];
            if (ch[x ^ 1]) ch[x ^ 1]->fa = old;
            ch[x ^ 1] = old;
            old->fa = this;
        }
        void splay() {
            while (fa) {
                if (fa->fa) fa->fa->pushDown();
                fa->pushDown();
                if (!fa->fa) rotate();
                else if (fa->relation() == relation()) fa->rotate(), rotate();
                else rotate(), rotate();
            }
        }
        void expose() {
            splay();
            pushDown();
            if (ch[1]) {
                std::swap(ch[1]->pathFa, ch[1]->fa);
                ch[1] = NULL;
            }
        }
        bool splice() {
            splay();
            if (!pathFa) return false;
            pathFa->expose();
            pathFa->ch[1] = this;
            std::swap(pathFa, fa);
            return true;
        }
        void access() {
            expose();
            while (splice());
        }
        void evert() {
            access();
            splay();
            rev ^= 1;
        }
    } N[MAXN + 1];
    void link(int a, int b) {
        Node *u = &N[a], *v = &N[b];
        u->evert();
        u->pathFa = v;
    }
    void cut(int a, int b) {
        Node *u = &N[a], *v = &N[b];
        u->evert();
        v->access();
        u->splay();
        u->pushDown();
        u->ch[1] = NULL;
        v->fa = NULL;
    }
    int find(int a) {
        Node *v = &N[a];
        v->access();
        v->splay();
        while (v->pushDown(), v->ch[0]) v = v->ch[0];
        return v - N;
    }
} lct;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        char s[8];
        int u, v;
        scanf("%s %d %d", s, &u, &v);
        if (s[0] == 'C') lct.link(u, v);
        else if (s[0] == 'D') lct.cut(u, v);
        else if (s[0] == 'Q') puts(lct.find(u) == lct.find(v) ? "Yes" : "No");
    }
    return 0;
}