题目1：BZOJ 2049 洞穴勘测
1 #include2 #define L(x) c[x][0] 3 #define R(x) c[x][1] 4 5 using namespace std; 6 7 const int oo = 0x3f3f3f3f; 8 9 struct SplayTree{ 10 static const int N = 10000 + 5; 11 12 int top, st[N]; 13 int fa[N], c[N][2], sum[N], mx[N], val[N]; 14 bool rev[N]; 15 16 bool isroot(int x){ 17 return L(fa[x]) != x && R(fa[x]) != x; 18 } 19 20 void pushdown(int x){ 21 int l = L(x), r = R(x); 22 23 if(rev[x]){ 24 rev[x] ^= 1; rev[l] ^= 1; rev[r] ^= 1; 25 swap(L(x), R(x)); 26 } 27 } 28 29 void pushup(int x){ 30 int l = L(x), r = R(x); 31 32 sum[x] = sum[l] + sum[r] + val[x]; 33 mx[x] = max(val[x], max(mx[l], mx[r])); 34 } 35 36 void rotate(int x){ 37 int y = fa[x], z = fa[y], l, r; 38 39 l = (L(y) == x) ^ 1; r = l ^ 1; 40 if(!isroot(y)) 41 c[z][(L(z) == y) ^ 1] = x; 42 fa[x] = z; fa[y] = x; fa[c[x][r]] = y; 43 c[y][l] = c[x][r]; c[x][r] = y; 44 } 45 46 void splay(int x){ 47 top = 0; 48 st[++ top] = x; 49 for(int i = x; !isroot(i); i = fa[i]) 50 st[++ top] = fa[i]; 51 while(top) pushdown(st[top --]); 52 while(!isroot(x)){ 53 int y = fa[x], z = fa[y]; 54 55 if(!isroot(y)){ 56 if(L(y) == x ^ L(z) == y) rotate(x); 57 else rotate(y); 58 } 59 rotate(x); 60 } 61 } 62 }Splay; 63 64 struct LinkCutTree{ 65 66 void Access(int x){ 67 int t = 0; 68 69 while(x){ 70 Splay.splay(x); 71 Splay.R(x) = t; 72 t = x; x = Splay.fa[x]; 73 } 74 } 75 76 void makeroot(int x){ 77 Access(x); Splay.splay(x); Splay.rev[x] ^= 1; 78 } 79 80 void link(int x, int y){ 81 makeroot(x); Splay.fa[x] = y; Splay.splay(x); 82 } 83 84 void cut(int x, int y){ 85 makeroot(x); Access(y); Splay.splay(y); 86 Splay.L(y) = Splay.fa[x] = 0; 87 } 88 89 int findroot(int x){ 90 Access(x); Splay.splay(x); 91 int y = x; 92 while(Splay.L(y)) y = Splay.L(y); 93 94 return y; 95 } 96 }lct; 97 98 int n, m, x, y; 99 char str[10];100 101 int main(){102 scanf("%d%d", &n, &m);103 for(int i = 1; i <= m; ++ i){104 scanf("%s%d%d", str, &x, &y);105 106 if(str[0] == 'C') lct.link(x, y);107 else if(str[0] == 'D') lct.cut(x, y);108 else{109 if(lct.findroot(x) == lct.findroot(y)) printf("Yes\n");110 else printf("No\n");111 }112 }113 114 return 0;115 }
题目2： BZOJ 1180 OTOCI
1 #include2 #define L(x) c[x][0] 3 #define R(x) c[x][1] 4 5 using namespace std; 6 7 typedef long long ll; 8 const int N = 30000 + 5; 9 const int oo = 0x3f3f3f3f; 10 11 struct SplayTree{ 12 int fa[N], c[N][2]; 13 ll val[N], mx[N], sum[N]; 14 bool rev[N]; 15 int top, st[N]; 16 17 inline bool isroot(int x){ 18 return L(fa[x]) != x && R(fa[x]) != x; 19 } 20 21 void pushdown(int x){ 22 int l = L(x), r = R(x); 23 24 if(rev[x]){ 25 rev[x] ^= 1; rev[l] ^= 1; rev[r] ^= 1; 26 swap(L(x), R(x)); 27 } 28 } 29 30 void pushup(int x){ 31 int l = L(x), r = R(x); 32 33 sum[x] = sum[l] + sum[r] + val[x]; 34 mx[x] = max(val[x], max(mx[l], mx[r])); 35 } 36 37 void rotate(int x){ 38 int y = fa[x], z = fa[y], l, r; 39 40 l = (L(y) == x) ^ 1; r = l ^ 1; 41 if(!isroot(y)){ 42 c[z][(L(z) == y) ^ 1] = x; 43 } 44 fa[x] = z; fa[y] = x; fa[c[x][r]] = y; 45 c[y][l] = c[x][r]; c[x][r] = y; 46 pushup(y); pushup(x); 47 } 48 49 void splay(int x){ 50 top = 0; 51 st[++ top] = x; 52 53 for(int i = x; !isroot(i); i = fa[i]) 54 st[++ top] = fa[i]; 55 while(top) pushdown(st[top --]); 56 while(!isroot(x)){ 57 int y = fa[x], z = fa[y]; 58 59 if(!isroot(y)){ 60 if(L(y) == x ^ L(z) == y) rotate(x); 61 else rotate(y); 62 } 63 rotate(x); 64 } 65 } 66 }Splay; 67 68 struct LinkCutTree{ 69 void Access(int x){ 70 int t = 0; 71 72 while(x){ 73 Splay.splay(x); 74 Splay.R(x) = t; 75 t = x; 76 Splay.pushup(x); 77 x = Splay.fa[x]; 78 } 79 } 80 81 void makeroot(int x){ 82 Access(x); Splay.splay(x); Splay.rev[x] ^= 1; 83 } 84 85 void link(int x, int y){ 86 makeroot(x); Splay.fa[x] = y; Splay.splay(x); 87 } 88 89 void cut(int x, int y){ 90 makeroot(x); Access(y); Splay.splay(y); 91 Splay.L(y) = Splay.fa[x] = 0; 92 } 93 94 int findroot(int x){ 95 Access(x); Splay.splay(x); 96 97 int y = x; 98 99 while(Splay.L(y)){100 y = Splay.L(y);101 }102 103 return y;104 }105 }lct;106 107 int n, m, x, y;108 char str[20];109 110 int main(){111 scanf("%d", &n);112 for(int i = 1; i <= n; ++ i){113 scanf("%lld", &Splay.val[i]);114 Splay.sum[i] = Splay.val[i];115 }116 scanf("%d", &m);117 for(int i = 1; i <= m; ++ i){118 scanf("%s%d%d", str, &x, &y);119 120 if(str[0] == 'b'){121 if(lct.findroot(x) == lct.findroot(y))122 puts("no");123 else{124 puts("yes"); lct.link(x, y);125 } 126 }127 else if(str[0] == 'e'){128 if(lct.findroot(x) != lct.findroot(y)){129 puts("impossible");130 }131 else{132 lct.makeroot(x); lct.Access(y); Splay.splay(y);133 printf("%lld\n", Splay.sum[y]);134 }135 }136 else{137 lct.makeroot(x); Splay.val[x] = y; Splay.pushup(x);138 }139 }140 141 return 0;142 }
题目3：BZOJ 3282 TREE
1 #include2 #define L(x) c[x][0] 3 #define R(x) c[x][1] 4 5 using namespace std; 6 7 const int N = 300000 + 5; 8 9 struct SplayTree{ 10 int fa[N], c[N][2], val[N], sum[N]; 11 bool rev[N]; 12 int top, st[N]; 13 14 inline bool isroot(int x){ 15 return L(fa[x]) != x && R(fa[x]) != x; 16 } 17 18 void pushup(int x){ 19 int l = L(x), r = R(x); 20 21 sum[x] = sum[l] ^ sum[r] ^ val[x]; 22 } 23 void pushdown(int x){ 24 int l = L(x), r = R(x); 25 26 if(rev[x]){ 27 rev[x] ^= 1; rev[l] ^= 1; rev[r] ^= 1; 28 swap(L(x), R(x)); 29 } 30 } 31 void rotate(int x){ 32 int y = fa[x], z = fa[y], l, r; 33 34 l = (L(y) == x) ^ 1; r = l ^ 1; 35 36 if(!isroot(y)){ 37 c[z][(L(z) == y) ^ 1] = x; 38 } 39 fa[y] = x; fa[x] = z; fa[c[x][r]] = y; 40 c[y][l] = c[x][r]; c[x][r] = y; 41 pushup(y); pushup(x); 42 } 43 44 void splay(int x){ 45 top = 0; 46 st[++ top] = x; 47 for(int i = x; !isroot(i); i = fa[i]) 48 st[++ top] = fa[i]; 49 50 while(top) pushdown(st[top --]); 51 while(!isroot(x)){ 52 int y = fa[x], z = fa[y]; 53 54 if(!isroot(y)){ 55 if(L(y) == x ^ L(z) == y) rotate(x); 56 else rotate(y); 57 } 58 rotate(x); 59 } 60 } 61 }Splay; 62 63 struct LinkCutTree{ 64 void Access(int x){ 65 int t = 0; 66 67 while(x){ 68 Splay.splay(x); 69 Splay.R(x) = t; 70 t = x; 71 Splay.pushup(x); 72 x = Splay.fa[x]; 73 } 74 } 75 76 void makeroot(int x){ 77 Access(x); Splay.splay(x); Splay.rev[x] ^= 1; 78 } 79 80 int findroot(int x){ 81 Access(x); Splay.splay(x); 82 83 int y = x; 84 85 while(Splay.L(y)) y = Splay.L(y); 86 87 return y; 88 } 89 90 void link(int x, int y){ 91 makeroot(x); Splay.fa[x] = y; Splay.splay(x); 92 } 93 94 void cut(int x, int y){ 95 makeroot(x); Access(y); Splay.splay(y); 96 Splay.L(y) = Splay.fa[x] = 0; 97 } 98 }lct; 99 100 int n, m;101 int x, y, z;102 103 int main(){104 scanf("%d%d", &n, &m);105 for(int i = 1; i <= n; ++ i){106 scanf("%d", &Splay.val[i]);107 Splay.sum[i] = Splay.val[i];108 }109 for(int i = 1; i <= m; ++ i){110 scanf("%d%d%d", &z, &x, &y);111 112 switch(z){113 case 0:{114 lct.makeroot(x); lct.Access(y); Splay.splay(y);115 printf("%d\n", Splay.sum[y]);116 break;117 }118 case 1:{119 if(lct.findroot(x) != lct.findroot(y)){120 lct.link(x, y);121 }122 break;123 }124 case 2:{125 if(lct.findroot(x) == lct.findroot(y)){126 lct.cut(x, y);127 }128 break;129 }130 case 3:{131 lct.Access(x); Splay.splay(x); Splay.val[x] = y;132 Splay.pushup(x);133 break;134 }135 }136 }137 138 return 0;139 }
题目4： HDU 4010 Query On The Trees
1 #include2 #include 3 #include 4 #include 5 #include 6 #define L(x) c[x][0] 7 #define R(x) c[x][1] 8 9 using namespace std; 10 11 const int N = 300000 + 5; 12 const int oo = 0x3f3f3f3f; 13 14 int n, m, tot; 15 int first[N], nxt[N<<1]; 16 int u[N<<1], v[N<<1]; 17 int que[N<<1]; 18 19 struct SplayTree{ 20 int fa[N], c[N][2], val[N], mx[N], add[N]; 21 bool rev[N]; 22 int top, st[N]; 23 24 inline bool isroot(int x){ 25 return L(fa[x]) != x && R(fa[x]) != x; 26 } 27 28 void pushup(int x){ 29 int l = L(x), r = R(x); 30 31 mx[x] = max(mx[l], mx[r]); 32 mx[x] = max(mx[x], val[x]); 33 } 34 35 void pushdown(int x){ 36 int l = L(x), r = R(x); 37 38 if(rev[x]){ 39 rev[x] ^= 1; rev[l] ^= 1; rev[r] ^= 1; 40 swap(L(x), R(x)); 41 } 42 if(add[x]){ 43 if(l){ 44 add[l] += add[x]; mx[l] += add[x]; val[l] += add[x]; 45 } 46 if(r){ 47 add[r] += add[x]; mx[r] += add[x]; val[r] += add[x]; 48 } 49 add[x] = 0; 50 } 51 } 52 53 void rotate(int x){ 54 int y = fa[x], z = fa[y], l, r; 55 56 l = (L(y) == x) ^ 1; r = l ^ 1; 57 if(!isroot(y)){ 58 c[z][L(z) == y ^ 1] = x; 59 } 60 fa[x] = z; fa[y] = x; fa[c[x][r]] = y; 61 c[y][l] = c[x][r]; c[x][r] = y; 62 pushup(y); pushup(x); 63 } 64 65 void splay(int x){ 66 top = 0; 67 st[++ top] = x; 68 for(int i = x; !isroot(i); i = fa[i]) 69 st[++ top] = fa[i]; 70 while(top) pushdown(st[top --]); 71 while(!isroot(x)){ 72 int y = fa[x], z = fa[y]; 73 74 if(!isroot(y)){ 75 if(L(y) == x ^ L(z) == y) rotate(x); 76 else rotate(y); 77 } 78 rotate(x); 79 } 80 } 81 }Splay; 82 83 struct LinkCutTree{ 84 void Access(int x){ 85 int t = 0; 86 87 while(x){ 88 Splay.splay(x); 89 Splay.R(x) = t; 90 t = x; 91 Splay.pushup(x); 92 x = Splay.fa[x]; 93 } 94 } 95 void Add(int x, int y, int w){ 96 makeroot(x); Access(y); Splay.splay(y); 97 Splay.add[y] += w; Splay.val[y] += w; 98 Splay.mx[y] += w; 99 }100 int findroot(int x){101 Access(x); Splay.splay(x);102 103 int y = x;104 105 while(Splay.L(y)){106 y = Splay.L(y);107 }108 109 return y;110 }111 112 void makeroot(int x){113 Access(x); Splay.splay(x); Splay.rev[x] ^= 1;114 }115 116 void cut(int x, int y){117 makeroot(x); Access(y); Splay.splay(y);118 Splay.L(y) = Splay.fa[Splay.L(y)] = 0; Splay.pushup(y);119 }120 121 void link(int x, int y){122 makeroot(x); Splay.fa[x] = y; Splay.splay(x);123 }124 }lct;125 126 void insert(int s, int t){127 ++ tot;128 u[tot] = s; v[tot] = t;129 nxt[tot] = first[s];130 first[s] = tot;131 }132 133 void bfs(){134 int head, tail;135 head = tail = 1;136 que[head] = 1;137 Splay.fa[1] = 0;138 139 while(head <= tail){140 int x = que[head];141 142 for(int i = first[x]; i; i = nxt[i]){143 if(v[i] != Splay.fa[x]){144 Splay.fa[v[i]] = x;145 que[++ tail] = v[i];146 }147 }148 ++ head;149 }150 }151 152 int main(){153 int flag, x, y, z;154 155 while(~scanf("%d", &n)){156 tot = 0;157 for(int i = 0; i <= n; ++ i){158 Splay.fa[i] = Splay.val[i] = Splay.add[i] = 0;159 Splay.rev[i] = false;160 Splay.mx[i] = -oo;161 Splay.c[i][0] = Splay.c[i][1] = 0;162 first[i] = 0;163 }164 for(int i = 1; i < n; ++ i){165 scanf("%d%d", &x, &y);166 insert(x, y); insert(y, x);167 }168 for(int i = 1; i <= n; ++ i){169 scanf("%d", &x);170 Splay.val[i] = Splay.mx[i] = x;171 }172 bfs();173 174 scanf("%d", &m);175 for(int i = 1; i <= m; ++ i){176 scanf("%d", &flag);177 switch(flag){178 case 1:{179 scanf("%d%d", &x, &y);180 if(lct.findroot(x) == lct.findroot(y))181 puts("-1");182 else183 lct.link(x, y);184 break;185 }186 case 2:{187 scanf("%d%d", &x, &y);188 if(lct.findroot(x) != lct.findroot(y) || x == y)189 puts("-1");190 else lct.cut(x, y);191 break;192 }193 case 3:{194 scanf("%d%d%d", &z, &x, &y);195 if(lct.findroot(x) != lct.findroot(y))196 puts("-1");197 else198 lct.Add(x, y, z);199 break;200 }201 case 4:{202 scanf("%d%d", &x, &y);203 if(lct.findroot(x) != lct.findroot(y))204 puts("-1");205 else{206 lct.makeroot(x); lct.Access(y); Splay.splay(y);207 printf("%d\n", Splay.mx[y]);208 }209 break;210 }211 }212 }213 puts("");214 }215 216 return 0;217 }