先要%mmh学长
一、模板：P3690 【模板】Link Cut Tree （动态树）：
题目背景
动态树

题目描述
给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

输入格式
第1行两个整数，分别为n和m，代表点数和操作数。

第2行到第n+1行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。

第n+2行到第n+m+1行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式
对于每一个0号操作，你须输出x到y的路径上点权的xor和。

输入输出样例
输入 #1 复制
3 3
1
2
3
1 1 2
0 1 2
0 1 1
输出 #1 复制
3
1
说明/提示
数据范围： 1≤N≤1e5,1≤m≤3×1e5

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
struct node
{
    int son[2];
    int fa;
    int val;
    int sum;
    int rev;
}t[maxn];
int st[maxn];

void pushup(int x)
{
    t[x].sum=t[t[x].son[0]].sum^t[t[x].son[1]].sum^t[x].val;
}

void _reverse(int x)
{
    if(!x) return ;
    swap(t[x].son[0],t[x].son[1]);
    t[x].rev^=1;
}

void pushdown(int x)
{
    if(!x) return ;
    if(t[x].rev)
    {
        _reverse(t[x].son[0]);
        _reverse(t[x].son[1]);
        t[x].rev=0;
    }
}

bool notroot(int x)
{
    return t[t[x].fa].son[0]==x||t[t[x].fa].son[1]==x;
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x)
{
    int y=t[x].fa,z=t[y].fa;
    int k=get_son(x),w=t[x].son[k^1];
    t[y].son[k]=w,t[w].fa=y;

    if(notroot(y))t[z].son[get_son(y)]=x;
    t[x].fa=z;

    t[x].son[k^1]=y,t[y].fa=x;
    pushup(y),pushup(x);
}

void splay(int x)
{
    int top=0;
    st[++top]=x;
    for(int pos=x;notroot(pos);pos=t[pos].fa) st[++top]=t[pos].fa;
    while(top) pushdown(st[top--]);

    while(notroot(x))
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(notroot(y))
            if(get_son(x)==get_son(y)) rot(y);
            else rot(x);
        rot(x);
    }
}

void access(int x)
{
    for(int y=0;x;y=x,x=t[x].fa)
    {
        splay(x);
        t[x].son[1]=y;
        pushup(x);
    }
}

void makeroot(int x)
{
    access(x);
    splay(x);
    _reverse(x);
}

int findroot(int x)
{
    access(x);
    splay(x);
    while(t[x].son[0]) pushdown(x),x=t[x].son[0];
    splay(x);
    return x;
}

void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

bool link(int x,int y)
{
    makeroot(x);
    if(findroot(y)==x) return false;
    t[x].fa=y;
    return true;
}

bool cut(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x||t[y].fa!=x||t[y].son[0]) return false;
    t[y].fa=t[x].son[1]=0;
    pushup(x);
    return true;
}

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t[i].val);
        t[i].fa=t[i].son[0]=t[i].son[1]=t[i].rev=0;
        t[i].sum=t[i].val;
    }
    int op,x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)
        {
            split(x,y);
            printf("%d\n",t[y].sum);
        }
        else if(op==1)
        {
            link(x,y);
        }
        else if(op==2)
        {
            cut(x,y);
        }
        else if(op==3)
        {
            splay(x);
            t[x].val=y;
            pushup(x);
        }
    }
    return 0;
}