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

题目描述

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

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

代码

#include<bits/stdc++.h>
#define N 100010
#define fa(x) tr[x].p
#define lc(x) tr[x].s[0]
#define rc(x) tr[x].s[1]
#define notroot(x) lc(fa(x))==x||rc(fa(x))==x
using namespace std;
int n,m;
struct node{
    int s[2],p,v,sum;
    int tag;
}tr[N];
void pushup(int x){
    tr[x].sum = tr[lc(x)].sum ^ tr[x].v ^ tr[rc(x)].sum;
}
void pushdown(int x){
    if(tr[x].tag){
        swap(lc(x),rc(x));
        tr[lc(x)].tag ^= 1;
        tr[rc(x)].tag ^= 1;
        tr[x].tag = 0;
    }
}
void rotate(int x){
    int y = fa(x),z = fa(y);
    int k = rc(y) == x;
    if(notroot(y))
        tr[z].s[rc(z) == y] = x;
    fa(x) = z;
    tr[y].s[k] = tr[x].s[k ^ 1];
    fa(tr[x].s[k ^ 1]) = y;
    tr[x].s[k ^ 1] = y;
    fa(y) = x;
    pushup(y),pushup(x);
}
void pushall(int x){
    if(notroot(x)) pushall(fa(x));
    pushdown(x);
}
void splay(int x){//伸展 
    pushall(x);
    while(notroot(x)){
        int y = fa(x),z = fa(y);
        if(notroot(y))
            (rc(y) == x) ^ (rc(z) == y) ? rotate(x) : rotate(y);
        rotate(x); 
    }
}
void access(int x){//通路 
    for(int y = 0;x;){
        splay(x);
        rc(x) = y;
        pushup(x);
        y = x,x = fa(x);
    }
}
void makeroot(int x){//换根 
    access(x);
    splay(x);
    tr[x].tag ^= 1;
}
void split(int x,int y){//分离 
    makeroot(x);
    access(y);
    splay(y);
}
void output(int x,int y){
    split(x,y);
    printf("%d\n",tr[y].sum);
}
int findroot(int x){//找根 
    access(x);
    splay(x);
    pushdown(x);
    while(lc(x))
        pushdown(x),x = lc(x);
    splay(x);//防止卡链 
    return x;
}
void link(int x,int y){//连边 
    makeroot(x);
    if(findroot(y) != x) fa(x) = y;
}
void cut(int x,int y){//断边 
    makeroot(x);
    if(findroot(y) == x && fa(y) == x && !lc(y)){
        fa(y) = 0;
        pushup(x);
    }
}
void change(int x,int y){//修改 
    splay(x);
    tr[x].v = y;
    pushup(x);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&tr[i].v);
    while(m --){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op == 0){
            output(x,y);
        }
        else if(op == 1){
            link(x,y);
        }
        else if(op == 2){
            cut(x,y);
        }
        else{
            change(x,y);
        }
    }
    return 0;
}