Fork me on GitHub

「Link-Cut-Trees」LCT动态树学习笔记

发表于 | 分类于
字数统计: 676字 | 阅读时长 ≈ 4分钟

调了差不多一下午+晚上左右的LCT,算是搞懂了

感谢qxq巨爷的倾情讲解（大雾

LCT讲稿(无比生动版)

LUOGU P3690 LCT[模板]

Link there

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define lc ch[u][0]
#define rc ch[u][1]

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}

///------------------head------------------

int n,m,op;
const int MAXN = 3e5+10;
struct LinkCutTree{
    int ch[MAXN][2],sum[MAXN],rev[MAXN],w[MAXN],fa[MAXN];
    inline bool isRson(int u){return ch[fa[u]][1] == u;}
    inline bool isRoot(int u){return (ch[fa[u]][0] != u && ch[fa[u]][1] != u);}
    inline void Reverse(int u){rev[u] ^= 1;swap(lc,rc);}
    inline void pushdown(int u){if(rev[u]){if (lc) Reverse(lc); if(rc)Reverse(rc); rev[u]=0;}}
    inline void pushup(int u){sum[u]=sum[lc]^sum[rc]^w[u];}
    inline void Update(int u){if (!isRoot(u)) Update(fa[u]); pushdown(u);}
/* ----------- Splay part ------------*/
    inline void rotate(int u){
        int fau = fa[u],ffau = fa[fau],d = isRson(u);
        fa[u]=ffau; if (!isRoot(fau)) ch[ffau][isRson(fau)] = u;
        fa[ch[fau][d] = ch[u][d^1]] = fau;
        fa[ch[u][d^1] = fau] = u;
        pushup(fau); pushup(u);
    }
    inline void Splay(int u){ //边Splay边向根传递信息
        Update(u);
        for (;(!isRoot(u));rotate(u)){
            if (!isRoot(fa[u]))
            rotate(isRson(fa[u])==isRson(u)?fa[u]:u);
        }
    }
/* ----------- LCT part ------------*/
    inline void access(int u){
        for(int f = 0; u; f = u,u = fa[u]){
            Splay(u);
            rc = f;
            pushup(u);
        }
    }
    inline void makeroot(int u){access(u);Splay(u);Reverse(u);}
    inline int find(int u){access(u);Splay(u);while(lc)pushdown(u),u=lc;return u;}
    inline void split(int x,int y){makeroot(x);access(y);Splay(y);}
    inline void link(int x,int y){makeroot(x);fa[x]=y;}
    inline void cut(int u,int v){split(u,v);if(fa[u]==v&&(!rc))fa[u]=ch[v][0]=0;pushup(v);}
}LCT;
signed main(signed argc, char *argv[]){
    n=read(),m=read();
    rep(i,1,n) LCT.w[i]=read();
    rep(i,1,m)
    {
        int op=read(),x=read(),y=read();
        switch(op){
            case 0:{LCT.split(x,y);printf("%d\n",LCT.sum[y]);break;}
            case 1:{if(LCT.find(x) != LCT.find(y))LCT.link(x,y);break;}
            case 2:{if(LCT.find(x) == LCT.find(y))LCT.cut(x,y);break;}
            case 3:{LCT.w[x]=y;LCT.Splay(x);break;}
        }
    }
	return 0;
}

剩下的中考之后再补辣.