前置知识：Splay，树链剖分

$\huge{LCT}$

$简介$

LCT(Link/Cut-Tree)，又名实链剖分

用于解决动态树问题

$引入$

给定一棵树，要求以下操作：

1. 1 x y 代表询问从 $x$ 到 $y$ 的路径上的点的权值的和。
2. 2 x y 代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。
3. 3 x y 代表删除边 $(x,y)$，不保证边 $(x,y)$ 存在。
4. 4 x y 代表将点 $x$ 上的权值变成 $y$。

像这类问题，存在加边和删边操作，被称为动态树问题

$概念$

• 实边：为平衡时间复杂度而定义，无实际意义，每个节点连0，1，2条实边连向儿子
• 实链：由多条实边组成，构成一个$Splay$结构
• 虚边：连接两个实链
• 辅助树是可以在满足中序遍历、Splay 的性质下任意换根的。
• 虚实链变换可以轻松在辅助树上完成，这也就是实现了动态维护树链剖分。

$辅助树$

辅助树是由多个$Splay$构成的，多个辅助树结构就构成了森林

1. 辅助树由多棵 Splay 组成，每棵 Splay 维护原树中的一条路径，且中序遍历这棵 Splay 得到的点序列，从前到后对应原树“从上到下”的一条路径。
2. 原树每个节点与辅助树的 Splay 节点一一对应。
3. 辅助树的各棵 Splay 之间并不是独立的。每棵 Splay 的根节点的父亲节点本应是空，但在 LCT 中每棵 Splay 的根节点的父亲节点指向原树中 这条链 的父亲节点（即链最顶端的点的父亲节点）。这类父亲链接与通常 Splay 的父亲链接区别在于儿子认父亲，而父亲不认儿子，对应原树的一条 虚边。因此，每个连通块恰好有一个点的父亲节点为空。
4. 由于辅助树的以上性质，我们维护任何操作都不需要维护原树，辅助树可以在任何情况下拿出一个唯一的原树，我们只需要维护辅助树即可。

如图，现在我们有一棵原树

它的辅助树如下

$函数声明$

1. Splay系列函数
   • pushrev(x)反转函数，用于懒标记
   • PushUp(x)更新
   • PushDown(x)下传标记
   • rotate(x)旋转一次
   • splay(x)$Splay$核心操作
2. LCT操作
   • Access(x)将$x$与 根节点 的路径上所有边改为实边
   • IsRoot(x)判断$x$是否是所在Splay的根。
   • makeroot(x)将$x$变为原树的根。
   • findroot(x)查找原树根
   • split(x, y)使 x 与 y 在同一个 Splay 中
   • link(x, y)连接 x 与 y
   • cut(x, y)切断 x 与 y 之间的边

$Splay$

不多说，但有一点不一样，已在代码中标注

void pushrev(int x) // 翻转一次x
{
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].rev ^= 1;
}

void pushup(int x)
{
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum; // 这里以xor为例
}

void pushdown(int x)
{
    if (tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
        tr[x].rev = 0;
    }
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (!isroot(y))tr[z].s[tr[z].s[1] == y] = x; // 判断是否为实边
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x) 
{
    int top = 0, r = x;
    stk[++ top] = r; // 需要先下传标记
    while (!isroot(r)) stk[++ top] = r = tr[r].p;
    while (top)pushdown(stk[top -- ]);
    while (!isroot(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y))rotate(x);
            else rotate(y);
        rotate(x);  
    }
}

$Access(x)$

目的是让$x$与根节点属于同一个$Splay$中

即让$x$到根节点的所有边都变为实边

void access(int x) // 将 x 与 根节点 的路径上所有边改为实边
{
    int z = x;
    for (int y = 0; x; y = x, x = tr[x].p)
    {
        splay(x); // 将 x 转到所在Splay的根节点
        tr[x].s[1] = y; // 将 y 设为 x 的右儿子，所有路径上的点都为右儿子
        pushup(x); // 更新 x 节点
    }
    splay(z); // 使整棵树更平衡
}

$IsRoot(x)$

bool isroot(int x) // x是否是所在Splay的根节点
{
    return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}

$makeroot(x)$

在 $access(x)$ 中存在一个细节：所有路径上的点都为右儿子

由于辅助树上的节点按中序遍历标记深度，那么 $x$ 为最深的点

想要成为根，就要反转这颗 $Splay$

void makeroot(int x) // 将 x 变为原树的根节点
{
    access(x); // 将 x 与 根节点 的路径上所有边改为实边 
    pushrev(x); // 反转 x 所在的 Splay
}

$findroot(int x)$

目的为找原树的根

原树的根位于辅助树根节点所在$Splay$中深度最低的点

从辅助树根出发，只要有实边就向左走，最终到达的点即为根

int findroot(int x) // 查找原树根
{
    access(x); // 将 x 与 根节点 的路径上所有边改为实边 
    while (tr[x].s[0])pushdown(x), x = tr[x].s[0]; // 找到根节点
    splay(x); // 使整棵树更平衡
    return x; // 返回根节点
}

$split(x, y)$

• 将 x 变为原树的根节点
• 将 y 与 x 的路径上所有边改为实边

void split(int x, int y) // 使 x 与 y 在同一个 Splay 中
{
    makeroot(x); // 将 x 变为原树的根节点
    access(y); // 将 y 与 x 的路径上所有边改为实边 
}

$link/cut$

有了前面的函数，这两个函数很好解决

void link(int x, int y) // 连接 x 与 y
{
    makeroot(x); // 将 x 变为根节点
    if (findroot(y) != x)tr[x].p = y; // 连虚边
}

void cut(int x, int y) // 切断 x 与 y 之间的边
{
    makeroot(x); // 将 x 变为根节点
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0; // 删边
        pushup(x); // 更新
    }
}

$实现$

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
struct Node {
    int s[2], p, v;
    int sum, rev;
}tr[N];
int stk[N];

bool isroot(int x) // x是否是所在Splay的根节点
{
    return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}

void pushrev(int x) // 翻转一次x
{
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].rev ^= 1;
}

void pushup(int x)
{
    tr[x].sum = tr[tr[x].s[0]].sum ^ tr[x].v ^ tr[tr[x].s[1]].sum;
}

void pushdown(int x)
{
    if (tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
        tr[x].rev = 0;
    }
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (!isroot(y))tr[z].s[tr[z].s[1] == y] = x; // 判断是否为实边
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x) 
{
    int top = 0, r = x;
    stk[++ top] = r; // 先要下传标记
    while (!isroot(r)) stk[++ top] = r = tr[r].p;
    while (top)pushdown(stk[top -- ]);
    while (!isroot(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y))rotate(x);
            else rotate(y);
        rotate(x);  
    }
}

void access(int x) // 将 x 与 根节点 的路径上所有边改为实边
{
    int z = x;
    for (int y = 0; x; y = x, x = tr[x].p)
    {
        splay(x); // 将 x 转到所在Splay的根节点
        tr[x].s[1] = y; // 将 y 设为 x 的右儿子，所有路径上的点都为右儿子
        pushup(x); // 更新 x 节点
    }
    splay(z); // 使整棵树更平衡
}

void makeroot(int x) // 将 x 变为原树的根节点
{
    access(x); // 将 x 与 根节点 的路径上所有边改为实边 
    pushrev(x); // 反转 x 所在的 Splay
}

int findroot(int x) // 查找原树根
{
    access(x); // 将 x 与 根节点 的路径上所有边改为实边 
    while (tr[x].s[0])pushdown(x), x = tr[x].s[0]; // 找到根节点
    splay(x); // 使整棵树更平衡
    return x; // 返回根节点
}

void split(int x, int y) // 使 x 与 y 在同一个 Splay 中
{
    makeroot(x); // 将 x 变为原树的根节点
    access(y); // 将 y 与 x 的路径上所有边改为实边 
}

void link(int x, int y) // 连接 x 与 y
{
    makeroot(x); // 将 x 变为根节点
    if (findroot(y) != x)tr[x].p = y; // 连虚边
}

void cut(int x, int y) // 切断 x 与 y 之间的边
{
    makeroot(x); // 将 x 变为根节点
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0; // 删边
        pushup(x); // 更新
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )scanf("%d", &tr[i].v);
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if (t == 0)
        {
            split(x, y);
            printf("%d\n", tr[y].sum);
        }
        if (t == 1)link(x, y);
        if (t == 2)cut(x, y);
        if (t == 3)
        {
            splay(x);
            tr[x].v = y;
            pushup(x);
        }
    }
    return 0;
}