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

Code:

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
void setIO(string a){ freopen((a+".in").c_str(),"r",stdin);}
struct LCT{
    #define maxn 400007
    #define lson ch[o][0]
    #define rson ch[o][1]
    int ch[maxn][2], f[maxn], val[maxn], tag[maxn], sta[maxn], sumv[maxn];
    int get(int x){ return ch[f[x]][1] == x; }
    int Isroot(int x){ return !(ch[f[x]][0] == x || ch[f[x]][1] == x); }
    void pushup(int o) {sumv[0] = 0, sumv[o] = sumv[lson] ^ sumv[rson] ^ val[o], sumv[0] = 0; }
    void mark(int x){ if(x) swap(ch[x][0], ch[x][1]), tag[x] ^= 1;}
    void pushdown(int o) { if(tag[o]) mark(lson), mark(rson), tag[o] ^= 1;}
    void rotate(int o){
        int old = f[o], fold = f[old], which = get(o);
        if(!Isroot(old)) ch[fold][ch[fold][1] == old] = o;
        f[o] = fold;
        ch[old][which] = ch[o][which^1], f[ch[old][which]] = old;
        ch[o][which^1] = old, f[old] = o;
        pushup(old), pushup(o), pushup(fold);
    }
    void splay(int o){
        int v = 0, u;
        sta[++v] = o, u = o;
        while(!Isroot(u)) sta[++v] = f[u], u = f[u];
        while(v) pushdown(sta[v--]);
        u = f[u];
        for(int fa;(fa=f[o]) != u;rotate(o))
            if(f[fa] != u) rotate(get(fa)==get(o)?fa:o);
    }
    void Access(int u){ for(int y=0;u;y=u,u=f[u]) splay(u), ch[u][1]=y, pushup(u); }                              
    void makeRoot(int u){ Access(u), splay(u), mark(u); }
    void split(int x,int y){ makeRoot(x), Access(y),splay(y);}
    int findRoot(int x){
        int u = x;
        Access(x), splay(x);
        while(x) u = x, pushdown(x), x=ch[x][0];
        return u;
    }
    void link(int x,int y){makeRoot(x); if(findRoot(y)!=x) f[x]=y;}
    void cut(int x,int y){
        makeRoot(x);
        if(findRoot(y) == x && f[x] == y && ch[y][0] == x && !ch[x][1]) {
            f[x] = ch[y][0] = 0;
            pushup(y);
        }
    }
}tree;
int main(){  
    //setIO("input");
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n; ++i) scanf("%d",&tree.val[i]), tree.sumv[i]=tree.val[i];
    for(int i = 1;i <= m; ++i){
        int opt,x, y; 
        scanf("%d%d%d",&opt,&x,&y);
        switch(opt){
            case 0: { tree.split(x,y), printf("%d
",tree.sumv[y]);  break; }
            case 1: { tree.link(x,y);  break; }
            case 2: { tree.cut(x,y);  break; }
            case 3: { tree.splay(x), tree.val[x] = y, tree.pushup(x); break; }
        }
    }
    return 0;
}