CF上遇到一题需要这个
先学着Splay版本的，后续有机会再学Treap版本的

参考资料
QTREE解法的一些研究

基本

将树剖分，用数据结构维护链
常见的树剖因为维护的是静态树结构，因此可以用线段树
而要求维护动态的结构时，就得用Splay之类的动态数据结构了
对于Splay，很容易考虑区间查询及区间修改（需要能整体统计撤销的）
那么接下来就得考虑如何合理地进行剖分使复杂度正确

核心操作 Access(x)
将 x 到根的路径上全部变成实边，并且丢弃自己的所有儿子
具体步骤即：

  1. 将 x 转至其所在 Splay 的根
  2. 将父节点转至其所在 Splay 的根，随后替换掉其右儿子，即沿虚边将替换掉父节点的实儿子
  3. 断开右子树（其实可以不需要）
  4. 转到1
    这一操作的均摊复杂度是 O(logn) 的

换根 makeRoot(u)

  1. access(u)
  2. 将 u 的左子树翻转
  3. 断开左子树，连接虚边
  4. 更新信息

判连通 connected(u, v)
access(u) 并获取 Splay中最左节点（即根），对 access(v) 并同样获取最左节点，进行比较，相同则连通

连接 link(u, v)
首先要确保不连通

  1. makeRoot(u)
  2. 从 u 向 v 连一条虚边（v为父亲）

断开 cut(u, v)
首先要确保二者间存在边

  1. makeRoot(v), splay(u)
  2. 若 u 没有向上虚边，则断开 u 的左子树，更新信息
  3. 否则断开 u 向上的虚边
    情况 3 中，即 u 为 v 的虚儿子；情况 2 中 u 为 v 的实儿子

洛谷P3690 【模板】动态树（Link Cut Tree）

#include <iostream>
using namespace std;

const int MAX_N = 1E5 + 100;

class Node {
   public:
    int val = 0, tot = 0;
    bool flip = 0;
    Node *c[2], *p, *pp;

    Node() {
        c[0] = c[1] = 0;
        fix();
    }

    void pushFlip() {
        if (!flip) return;
        flip = 0;
        swap(c[0], c[1]);
        if (c[0]) c[0]->flip ^= 1;
        if (c[1]) c[1]->flip ^= 1;
    }

    void fix() {
        //维护的数据在这里处理
        tot = val;
        if (c[0]) {
            c[0]->p = this;
            tot ^= c[0]->tot;
        }
        if (c[1]) {
            c[1]->p = this;
            tot ^= c[1]->tot;
        }
    }

    int type() { return p ? this == p->c[1] : 2; }

    void rot(int i, int j) {
        bool b = i ^ j;
        Node *x = c[i], *y = 2 == j ? x : x->c[j], *z = b ? y : x;

        if (y->p = p) p->c[type()] = y;
        c[i] = z->c[i ^ 1];
        if (j < 2) {
            x->c[j] = y->c[j ^ 1];
            z->c[j ^ 1] = b ? x : this;
        }
        y->c[i ^ 1] = b ? this : x;

        fix();
        x->fix();
        y->fix();

        swap(pp, y->pp);
    }

    void splay() {
        for (pushFlip(); p;) {
            if (p->p) p->p->pushFlip();
            p->pushFlip();
            pushFlip();

            if (2 == p->type())
                p->rot(type(), 2);
            else
                p->p->rot(p->type(), type());
        }
    }

    Node *first() {
        pushFlip();
        return c[0] ? c[0]->first() : (splay(), this);
    }
};

class LCT {
   public:
    Node node[MAX_N];

    Node *access(Node *u) {
        for (u->splay(); Node *pp = u->pp; u = pp) {
            pp->splay();
            u->pp = 0;

            if (pp->c[1]) {
                pp->c[1]->p = 0;
                pp->c[1]->pp = pp;
            }
            pp->c[1] = u;
            pp->fix();
        }
        return u;
    }

    void makeRoot(Node *u) {
        access(u);
        u->splay();
        if (u->c[0]) {
            u->c[0]->flip ^= 1;
            u->c[0]->p = 0;
            u->c[0]->pp = u;
            u->c[0] = 0;
            u->fix();
        }
    }

    bool connected(Node *u, Node *v) {
        Node *ru = access(u)->first();
        return ru == access(v)->first();
    }

    void link(Node *u, Node *v) {
        if (connected(u, v)) return;
        makeRoot(u);
        u->pp = v;
    }

    void cut(Node *u, Node *v) {
        makeRoot(v);
        u->splay();
        if (v != (u->pp ?: u->c[0])) return;
        if (u->pp) {
            u->pp = 0;
        } else {
            u->c[0] = v->p = 0;
            u->fix();
        }
    }

    //===============

    Node *access(int u) { return access(node + u); }
    void makeRoot(int u) { makeRoot(node + u); }
    bool connected(int u, int v) { return connected(node + u, node + v); }
    void link(int u, int v) { link(node + u, node + v); }
    void cut(int u, int v) { cut(node + u, node + v); }
};

int n, m;
LCT tr;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> tr.node[i].val;
        tr.node[i].tot = tr.node[i].val;
    }

    while (m--) {
        int u, v, opt;
        cin >> opt >> u >> v;
        if (0 == opt) {
            tr.makeRoot(u);
            tr.access(v);
            tr.node[v].splay();
            cout << (tr.node[v].tot ^
                     (tr.node[v].c[1] ? tr.node[v].c[1]->tot : 0))
                 << '\n';
        } else if (1 == opt) {
            tr.link(u, v);
        } else if (2 == opt) {
            tr.cut(u, v);
        } else {
            tr.node[u].splay();
            tr.node[u].tot ^= tr.node[u].val;
            tr.node[u].val = v;
            tr.node[u].tot ^= v;
        }
    }

    return 0;
}

CF1555EDU F. Good Graph