Time Limit: 25 Sec Memory Limit: 128 MB
Submit: 1725 Solved: 526
1 int getint() { 2 char ch = getchar(); 3 for ( ; ch > ‘9‘ || ch < ‘0‘; ch = getchar()); 4 int tmp = 0; 5 for ( ; ‘0‘ <= ch && ch <= ‘9‘; ch = getchar()) 6 tmp = tmp * 10 + int(ch) - 48; 7 return tmp; 8 }
解题：LCT，离线逆序操作，将删边转为加边，用点代表边
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 2000010; 4 struct LCT{ 5 int fa[maxn],ch[maxn][2],parent[maxn],flip[maxn],mx[maxn]; 6 int val[maxn]; 7 inline void pushdown(int x){ 8 if(!x) return; 9 if(flip[x]){ 10 if(ch[x][0]) flip[ch[x][0]] ^= 1; 11 if(ch[x][1]) flip[ch[x][1]] ^= 1; 12 swap(ch[x][0],ch[x][1]); 13 flip[x] = 0; 14 } 15 } 16 inline void pushup(int x){ 17 if(!x) return; 18 mx[x] = x; 19 if(ch[x][0] && val[mx[ch[x][0]]] > val[mx[x]]) mx[x] = mx[ch[x][0]]; 20 if(ch[x][1] && val[mx[ch[x][1]]] > val[mx[x]]) mx[x] = mx[ch[x][1]]; 21 } 22 void rotate(int x,int kd){ 23 int y = fa[x]; 24 pushdown(y); 25 pushdown(x); 26 ch[y][kd^1] = ch[x][kd]; 27 fa[ch[x][kd]] = y; 28 fa[x] = fa[y]; 29 if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x; 30 ch[x][kd] = y; 31 fa[y] = x; 32 pushup(y); 33 } 34 void splay(int x,int goal = 0){ 35 pushdown(x); 36 int y = x; 37 while(fa[y]) y = fa[y]; 38 if(x != y){ 39 parent[x] = parent[y]; 40 parent[y] = 0; 41 while(fa[x] != goal){ 42 pushdown(fa[fa[x]]); 43 pushdown(fa[x]); 44 if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]); 45 else{ 46 int y = fa[x],z = fa[y],s = (y == ch[z][0]); 47 if(x == ch[y][s]){ 48 rotate(x,s^1); 49 rotate(x,s); 50 }else{ 51 rotate(y,s); 52 rotate(x,s); 53 } 54 } 55 } 56 } 57 pushup(x); 58 } 59 void access(int x){ 60 for(int y = 0; x; x = parent[x]){ 61 splay(x); 62 fa[ch[x][1]] = 0; 63 parent[ch[x][1]] = x; 64 parent[y] = 0; 65 ch[x][1] = y; 66 fa[y] = x; 67 y = x; 68 pushup(x); 69 } 70 } 71 int findroot(int x){ 72 access(x); 73 splay(x); 74 while(ch[x][0]) x = ch[x][0]; 75 return x; 76 } 77 void makeroot(int x){ 78 access(x); 79 splay(x); 80 flip[x] ^= 1; 81 } 82 void cut(int x,int y){ 83 makeroot(x); 84 access(y); 85 splay(y); 86 fa[ch[y][0]] = 0; 87 ch[y][0] = 0; 88 pushup(y); 89 } 90 void link(int x,int y){ 91 makeroot(y); 92 parent[y] = x; 93 access(y); 94 } 95 int Q(int x,int y){ 96 makeroot(x); 97 access(y); 98 splay(y); 99 return mx[y]; 100 } 101 }lct; 102 struct arc{ 103 int u,v,w,id; 104 bool del; 105 }e[1000005]; 106 struct QU{ 107 int u,v,id,op,ans; 108 }Q[100005]; 109 void read(int &tmp) { 110 char ch = getchar(); 111 for (; ch>‘9‘||ch<‘0‘; ch=getchar()); 112 tmp = 0; 113 for (; ‘0‘<=ch&&ch<=‘9‘; ch=getchar()) 114 tmp=tmp*10+int(ch)-48; 115 } 116 bool cmp(const arc &a,const arc &b){ 117 return a.w < b.w; 118 } 119 bool cmp2(const arc &a,const arc &b){ 120 if(a.u == b.u) return a.v < b.v; 121 return a.u < b.u; 122 } 123 bool cmp3(const arc &a,const arc &b){ 124 return a.id < b.id; 125 } 126 int n,m,q,uf[maxn]; 127 int bsearch(int u,int v){ 128 int low = 1,high = m; 129 while(low <= high){ 130 int mid = (low + high)>>1; 131 if(e[mid].u == u && e[mid].v == v) return mid; 132 if(e[mid].u < u || e[mid].u == u && e[mid].v < v) low = mid + 1; 133 else high = mid - 1; 134 } 135 } 136 int Find(int x){ 137 if(x != uf[x]) uf[x] = Find(uf[x]); 138 return uf[x]; 139 } 140 int main(){ 141 read(n); 142 read(m); 143 read(q); 144 for(int i = 1; i <= m; ++i){ 145 read(e[i].u); 146 read(e[i].v); 147 read(e[i].w); 148 if(e[i].u > e[i].v) swap(e[i].u,e[i].v); 149 } 150 sort(e + 1,e + 1 + m,cmp); 151 for(int i = 1; i <= m; ++i){ 152 e[i].id = i; 153 lct.val[n + i] = e[i].w; 154 lct.mx[n + i] = n + i; 155 } 156 for(int i = 0; i <= n + m; ++i) uf[i] = i; 157 sort(e + 1,e + 1 + m,cmp2); 158 for(int i = 1; i <= q; ++i){ 159 read(Q[i].op); 160 read(Q[i].u); 161 read(Q[i].v); 162 if(Q[i].u > Q[i].v) swap(Q[i].u,Q[i].v); 163 if(Q[i].op == 2){ 164 int t = bsearch(Q[i].u,Q[i].v); 165 e[t].del = true; 166 Q[i].id = e[t].id; 167 } 168 } 169 sort(e + 1,e + 1 + m,cmp3); 170 int cnt = 0; 171 for(int i = 1; i <= m; ++i){ 172 if(!e[i].del){ 173 int u = Find(e[i].u); 174 int v = Find(e[i].v); 175 if(u == v) continue; 176 uf[u] = v; 177 lct.link(u,n + i); 178 lct.link(v,n + i); 179 if(++cnt == n - 1) break; 180 } 181 } 182 for(int i = q; i > 0; --i){ 183 if(Q[i].op == 1) Q[i].ans = lct.val[lct.Q(Q[i].u,Q[i].v)]; 184 else{ 185 int x = Q[i].u,y = Q[i].v,k = Q[i].id; 186 int t = lct.Q(x,y); 187 if(e[k].w < lct.val[t]){ 188 lct.cut(e[t-n].u,t); 189 lct.cut(e[t-n].v,t); 190 lct.link(Q[i].u,k + n); 191 lct.link(Q[i].v,k + n); 192 } 193 } 194 } 195 for(int i = 1; i <= q; ++i) 196 if(Q[i].op == 1) printf("%d\n",Q[i].ans); 197 return 0; 198 } 199 /* 200 4 4 3 201 1 2 2 202 2 3 3 203 3 4 2 204 1 4 2 205 1 1 4 206 2 1 4 207 1 1 4 208 */
原文：http://www.cnblogs.com/crackpotisback/p/4920564.html
