本文主要通过板子题代码介绍 LCT 的实现过程与实现细节（Why），对 LCT 基础定义（What）不做讲解，作者水平有限，解释可能有误，望谅。

例题1.>luoguP3690

// LCT link-cut-tree 注释版ok
// 注意Splay中维护的是严格按中序遍历递增的节点深度
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m;
struct tree
{
    int ch[2], fa, sum, key, tag;
} t[maxn];

// 常规Splay操作
void pushup(int now)
{
    t[now].sum = t[t[now].ch[0]].sum ^ t[t[now].ch[1]].sum ^ t[now].key;
}

// 判断该点是否为当前splay的根，并非是判断原树的根
bool isroot(int now)
{
    //很简单，当父亲不认这个儿子时该点就是根
    return t[t[now].fa].ch[0] != now && t[t[now].fa].ch[1] != now;
}

//常规Splay操作
bool check(int now)
{
    return now == t[t[now].fa].ch[1];
}

//常规Splay操作
void pushdown(int now)
{
    if (t[now].tag)
    {
        swap(t[now].ch[0], t[now].ch[1]);
        t[now].tag ^= 1;
        t[t[now].ch[0]].tag ^= 1, t[t[now].ch[1]].tag ^= 1;
    }
}

//每次作Splay前一定要提前从根传标记修改，递归实现即可
void update(int now)
{
    if (!isroot(now))
        update(t[now].fa);
    pushdown(now);
}

//常规旋转操作，就是主要一下判根不能简单的用0来判，要用isroot来判
void rotate(int now)
{
    int f = t[now].fa, gf = t[f].fa, flag = check(now);
    if (!isroot(f))
        t[gf].ch[f == t[gf].ch[1]] = now;
    t[t[now].ch[flag ^ 1]].fa = f, t[f].ch[flag] = t[now].ch[flag ^ 1], t[now].ch[flag ^ 1] = f;
    t[f].fa = now, t[now].fa = gf; //记得无论旋转后的now是不是根，都一定要连gf
    pushup(f);
    pushup(now);
}

//常规操作，注意到根的终止情况，记得要先自根向下修改
void splay(int now)
{
    //记得先自顶向下把标记传完！
    update(now);
    for (int f = t[now].fa; !isroot(now); rotate(now), f = t[now].fa)
    {
        if (!isroot(f)) //f是根了，跳过，只转now就行
        {
            if (check(f) == check(now)) //三点共侧，常规转father
                rotate(f);
            else
                rotate(now);
        }
    }
}

//重点操作，将根到当前节点的路径全部改成实链（搞到1棵Splay上）
void access(int now)
{
    for (int i = 0; now; i = now, now = t[now].fa)
    {
        splay(now);       //将当前节点旋转到当前Splay的根，此时Splay无右儿子-->没有比当前节点深度大的点
        t[now].ch[1] = i; //抛弃原来的右儿子，将右儿子改为上一个Splay的根-->合并到了一个Splay里
        pushup(now);      //记得更新
    }
}

//重点操作，换 原树 原树 原树 的根！
//为什么要换根-->因为路径不保证深度严格递增
void makeroot(int now)
{
    //打通原根到该点的路径，搞到一棵Splay里
    access(now);
    //将该点转到根上，注意换根的影响，会使原root->now的路径翻转，故打上翻转tag
    splay(now);
    t[now].tag ^= 1;
}

//找根操作，找当前节点在当前树(原树)上的根
int findroot(int x)
{
    //先打通路径
    access(x);
    //把x旋转到根上，显然此时x深度最大，无右子树，而根深度最小，故在最左的子树上
    splay(x);
    //记得先下传标记改左右子树，再找左子树
    pushdown(x);
    while (t[x].ch[0])
    {
        x = t[x].ch[0];
        //记得下传
        pushdown(x);
    }
    //把正经的根再旋回来！否则这棵可怜的Splay就歪了qaq，时间复杂度会炸的 
    splay(x);
    return x;
}

//重点操作 把x->y的路径拆出来，方便搞(对路径修改查询)
void split(int x, int y)
{
    //把原树上的根换成x
    makeroot(x);
    //把x->y的Splay搞出来
    access(y);
    //把y旋转到根，这样查啥都是在y上了
    splay(y);
}

//重点操作，连边
void link(int x, int y)
{
    //把x搞成原树的根，这样就可以直接连边了哈
    makeroot(x);
    //特判一下如果x,y在同一个连通块内，那就依题意不连
    if (x == findroot(y))
        return;
    //直接连上，这就是把它旋成根的好处，但记住只让x认y就行，y不用在此处认x
    t[x].fa = y;
}

//重点操作，删边
void cut(int x, int y)
{
    //把x搞成原树的根，方便下面的判断
    makeroot(x);
    //如果x,y不连通-->findroot(x) != y  x,y之间有其它点隔开-->t[y].ch[0]有值或t[y].fa != x
    //为什么要打findroot(y)？-->findroot(y)隐含了access(y)保证了接下来的验证
    //为什么要打t[y].fa!=x？-->很显然的啊，如果y是在这splay的叶子节点，那么依然满足剩余两个条件，但此时显然两者无边
    //为什么要打t[y].ch[0]？-->点的顺序是按深度设置的，如果y还有左子树的话那就说明在x,y这条路径上还有深度在x,y之间的点，那他俩就显然无边
    if (findroot(y) != x || t[y].fa != x || t[y].ch[0])
        return;
    //此时y是x的右子树，直接删就可以啦
    t[y].fa = t[x].ch[1] = 0;
    //可以不pushup，但pushup一下一定没错且更符合逻辑
    pushup(x);
}

//常规操作
int getsum(int x, int y)
{
    //把路径提出来，此时的y为该Splay的根，记录路径的信息
    split(x, y);
    return t[y].sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        //直接读入就好了
        cin >> t[i].key;
    }
    for (int i = 1; i <= m; i++)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 0)
        {
            cout << getsum(x, y) << "\n";
        }
        if (op == 1)
        {
            link(x, y);
        }
        if (op == 2)
        {
            cut(x, y);
        }
        if (op == 3)
        {
            //每次操作前把x先旋转到根，方便修改，保证正确性
            splay(x);
            t[x].key = y;
            //为什么直接改key值就可以？
            //因为每次查询前都会有access操作，一定会把路径上的节点都重pushup一遍，就保证了正确性
        }
    }
    return 0;
}
//by syj 2024 10 11