动态树Link-Cut-Tree
LCT要保证时时刻刻都是一棵树（图中自始至终无环出现）
bzoj2049
无根树LCT（Link和Cut的时候都要make_root，需要lazy-tag标记）
只维护连通性，父子关系不重要
维护fa(x) lc(x) rc(x) tag(x)
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define N 1000000using namespace std;int n, m;struct node{int fa, lc, rc, tag;#define fa(x) tr[x].fa#define lc(x) tr[x].lc#define rc(x) tr[x].rc#define tag(x) tr[x].tag}tr[N];inline int is_root(int x){if(!fa(x)) return 1;else return x != lc(fa(x)) && x != rc(fa(x));}inline int which(int x){return x == rc(fa(x));}inline void Rotate(int x){int y = fa(x);int z = fa(y);int s = x == lc(y) ? rc(x) : lc(x);if(!is_root(y)) (y == lc(z) ? lc(z) : rc(z)) = x;if(s) fa(s) = y;fa(y) = x;fa(x) = z;if(x == lc(y)) rc(x) = y, lc(y) = s;else lc(x) = y, rc(y) = s;}inline void pushdown(int x){if(tag(x)){tag(x) = 0;swap(lc(x), rc(x));if(lc(x)) tag(lc(x)) ^= 1;if(rc(x)) tag(rc(x)) ^= 1;}}int temp[N];inline void splay(int x){int cnt = 1;temp[1] = x;for(int z = x; !is_root(z); z = fa(z))temp[ cnt] = fa(z);for(int i=cnt; i; --i) pushdown(temp[i]);while(!is_root(x)){if(!is_root(fa(x))){if(which(x) == which(fa(x))) Rotate(fa(x));else Rotate(x);}Rotate(x);}}inline void Access(int x){int y = 0;while(x){splay(x);rc(x) = y;y = x;x = fa(x);}}inline int Find_root(int x){Access(x);splay(x);while(lc(x)) x = lc(x);return x;}inline void Make_root(int x){Access(x);splay(x);tag(x) ^= 1;}inline void Link(int x, int y){Make_root(x);fa(x) = y;}inline void Cut(int x, int y){Make_root(x);Access(y);splay(y);lc(y) = 0;fa(x) = 0;}int main(){scanf("%d%d", &n, &m);for(int i=1, x, y; i<=m; i){char opt[100];scanf("%s%d%d", opt, &x, &y);if(opt[0] == 'Q') printf(Find_root(x) == Find_root(y) ? "Yes\n" : "No\n");else if(opt[0] == 'C') Link(x, y);else Cut(x, y);}}hdu2475 有根树LCT
父子关系表示箱子的包含关系，所以父子关系不能随便颠倒，所以不能用make_root，不用make_root的话，也不用打lazy_tag标记了。
Cut里面只传一个参数x，表示减掉x和x父亲的连边
维护fa(x) lc(x) rc(x)
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define N 100000using namespace std;int n, m;struct node{int fa, lc, rc;#define fa(x) tr[x].fa#define lc(x) tr[x].lc#define rc(x) tr[x].rc}tr[N];inline int is_root(int x){if(!fa(x)) return 1;else return x != lc(fa(x)) && x != rc(fa(x));}inline int which(int x){return x == rc(fa(x));}inline void Rotate(int x){int y = fa(x);int z = fa(y);int s = x == lc(y) ? rc(x) : lc(x);if(!is_root(y)) (y == lc(z) ? lc(z) : rc(z)) = x;if(s) fa(s) = y;fa(y) = x;fa(x) = z;if(x == lc(y)) rc(x) = y, lc(y) = s;else lc(x) = y, rc(y) = s;}int temp[N];inline void splay(int x){int cnt = 1;temp[1] = x;for(int z = x; !is_root(z); z = fa(z))temp[ cnt] = fa(z);//for(int i=cnt; i; --i) pushdown(temp[i]);while(!is_root(x)){if(!is_root(fa(x))){if(which(x) == which(fa(x))) Rotate(fa(x));else Rotate(x);}Rotate(x);}}inline void Access(int x){int y = 0;while(x){splay(x);rc(x) = y;y = x;x = fa(x);}}inline int Find_root(int x){Access(x);splay(x);while(lc(x)) x = lc(x);return x;}inline void Cut(int x) //减掉x和x父亲的连边 {Access(x);splay(x);fa(lc(x)) = 0;lc(x) = 0;}inline void Link(int x, int y) {if(x == y) return;if(!y) Cut(x);else{Access(y);splay(y);int z = x;while(!is_root(z)) z = fa(z); // 只能在一条重链(一棵splay内)跳 if(z == y) return;Cut(x);fa(x) = y;}}int main(){int n, flag = 0;while(scanf("%d", &n) == 1){if(flag) printf("\n");flag = 1;for(int i=1; i<=n; i) lc(i) = rc(i) = 0; for(int i=1; i<=n; i) scanf("%d", &fa(i));int q;scanf("%d", &q);while(q--){char c[10];int x, y;scanf("%s%d", c, &x);if(c[0] == 'M'){scanf("%d", &y);Link(x, y);}else printf("%d\n", Find_root(x));//for(int i=1; i<=n; i) printf("%d %d %d\n", fa(i), lc(i), rc(i));}}} 赞 (0)