洛谷P3690 Link Cut Tree（LCT）

水深无声 2021-11-09 10:54 160阅读 0赞

## 题意： ##

## 给定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。 ##

## 分析：LCT模板题，LCT是解决动态树问题常用的数据结构。LCT=树链剖分+splay。入门推荐[https://www.cnblogs.com/flashhu/p/8324551.html。][https_www.cnblogs.com_flashhu_p_8324551.html] ##

## 代码： ##

#include<bits/stdc++.h>
    #define lc c[x][0]
    #define rc c[x][1]
    using namespace std;
    const int N=3e5+9;
    
    int f[N],c[N][2],v[N],s[N],st[N];
    bool r[N];
    ///判断节点是否为一个Splay的根（与普通Splay的区别1）
    bool nroot(int x){
        return c[f[x]][0]==x||c[f[x]][1]==x;
    }///原理很简单，如果连的是轻边，他的父亲的儿子里没有它
    
    ///上传信息
    void pushup(int x){
        s[x]=s[lc]^s[rc]^v[x];
    }
    
    ///翻转操作
    void pushr(int x){
        int t=lc;lc=rc;rc=t;r[x]^=1;
    }
    
    ///判断并释放懒标记
    void pushdown(int x){
        if(r[x]){
            if(lc)pushr(lc);
            if(rc)pushr(rc);
            r[x]=0;
        }
    }
    
    ///一次旋转
    void rotate(int x){
        int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
        if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;///额外注意if(nroot(y))语句，此处不判断会引起致命错误（与普通Splay的区别2）
        if(w)f[w]=y;f[y]=x;f[x]=z;
        pushup(y);
    }
    
    ///只传了一个参数，因为所有操作的目标都是该Splay的根（与普通Splay的区别3）
    void splay(int x){
        int y=x,z=0;
        st[++z]=y;///st为栈，暂存当前点到根的整条路径，pushdown时一定要从上往下放标记（与普通Splay的区别4）
        while(nroot(y))st[++z]=y=f[y];
        while(z)pushdown(st[z--]);
        while(nroot(x)){
            y=f[x];z=f[y];
            if(nroot(y))
                rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    
    ///访问
    void access(int x){
        for(int y=0;x;x=f[y=x])
            splay(x),rc=y,pushup(x);
    }
    
    ///换根
    void makeroot(int x){
        access(x);splay(x);
        pushr(x);
    }
    
    ///找根（在真实的树中的）
    int findroot(int x){
        access(x);splay(x);
        while(lc)pushdown(x),x=lc;
        splay(x);
        return x;
    }
    
    ///提取路径
    void split(int x,int y){
        makeroot(x);
        access(y);splay(y);
    }
    
    ///连边
    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[y]==x&&!c[y][0]){
            f[y]=c[x][1]=0;
            pushup(x);
        }
    }
    int n,m;
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
            scanf("%d",&v[i]);
        while(m--){
            int type,x,y;
            scanf("%d%d%d",&type,&x,&y);
            switch(type){
                case 0:split(x,y);printf("%d\n",s[y]);break;
                case 1:link(x,y);break;
                case 2:cut(x,y);break;
                case 3:splay(x);v[x]=y;///先把x转上去再改，不然会影响Splay信息的正确性
            }
        }
        return 0;
    }

[https_www.cnblogs.com_flashhu_p_8324551.html]: https://www.cnblogs.com/flashhu/p/8324551.html