Description：
SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。
在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。
不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。
传送门。
仍然没能自己想出来，LCT题果然都不一般。
做过的第三个时光倒流题，都没有想到，而且还一个题解都没有写，有必要积累一下思路。
时光倒流就是当某一种正向的操作不好进行时（往往是可插入不可删除的数据结构的删除操作）
倒序读入，倒序处理询问，使删除变成插入操作的技巧。
以本题为例，我们要维护的是最小生成树，过程当中会删除一些边。
我们会发现无法在可以接受的复杂度内找到一条边的替代品，删除操作的复杂度没有保证。
那么我们考虑时光倒流，先处理最后一个询问，这时候所有的被删的边都不在最小生成树里。
所以我们对询问里没有出现的边跑一个最小生成树就是答案。
然而删边操作就变成了把被删的边加回来，就是解锁，或者说加入一条边。
加入的话就好说了，我们只要查询一下在目前的生成树里两个端点之间的最大边权。
如果查询结果比加入的边权大，那么就在生成树里删除那条最没用的边，把新的这条边加入即可。
否则这条新边就是没用的，无需操作。
具体实现的话：连边，加边，查链上最大边权及对应的编号。
用lct实现就行。细节还有拿hash_map映射边啊什么的就比较简单了。
1 #include<cstdio> 2 #include<queue> 3 using namespace std; 4 #define lc c[p][0] 5 #define rc c[p][1] 6 int f[1200005],c[1200005][2],n,m,q,lz[1200005],mx[1200005],mxp[1200005],v[1200005]; 7 int sta[1200005],A[1000005],B[1000005],V[1000005],opt[100005],x[100005],y[100005]; 8 int lck[1000005],ans[1000005]; 9 struct hashmap{ 10 #define mod 2000003 11 int fir[2000005],l[2000005],x[2000005],y[2000005],v[2000005],cnt; 12 int &operator[](pair<int,int>p){ 13 int xx=p.first,yy=p.second; 14 if(xx<yy)xx^=yy^=xx^=yy; 15 long long hsh=(xx*19733737ll+yy)%mod; 16 for(int i=fir[hsh];i;i=l[i])if(x[i]==xx&&y[i]==yy)return v[i]; 17 l[++cnt]=fir[hsh];fir[hsh]=cnt;x[cnt]=xx;y[cnt]=yy;return v[cnt]; 18 } 19 }mm; 20 void read(int &p,register char ch=getchar()){ 21 while(ch>'9'||ch<'0')ch=getchar(); 22 while(ch<='9'&&ch>='0')p=(p<<3)+(p<<1)+ch-48,ch=getchar(); 23 } 24 bool not_root(int p){return c[f[p]][0]==p||c[f[p]][1]==p;} 25 void rev(int p){lc^=rc^=lc^=rc,lz[p]^=1;} 26 void up(int p){ 27 if(mx[lc]>mx[rc])mx[p]=mx[lc],mxp[p]=mxp[lc]; 28 else mx[p]=mx[rc],mxp[p]=mxp[rc]; 29 if(v[p]>mx[p])mx[p]=v[p],mxp[p]=p; 30 } 31 void down(int p){if(lz[p])rev(lc),rev(rc),lz[p]=0;} 32 void rotate(int p){ 33 int fa=f[p],gr=f[fa],k=c[fa][1]==p,br=c[p][!k]; 34 if(not_root(fa))c[gr][c[gr][1]==fa]=p; c[p][!k]=fa; c[fa][k]=br; 35 f[p]=gr; f[fa]=p; f[br]=fa; up(fa); 36 } 37 void splay(int p){ 38 int res=p,top=0;sta[++top]=p; 39 while(not_root(res))sta[++top]=res=f[res]; 40 while(top)down(sta[top--]); 41 while(not_root(p)){ 42 int fa=f[p],gr=f[fa]; 43 if(not_root(fa))rotate((c[fa][1]==p)^(c[gr][1]==fa)?fa:p); 44 rotate(p); 45 } 46 up(p); 47 } 48 void access(int p){for(int y=0;p;p=f[y=p])splay(p),rc=y,up(p);} 49 void make_root(int p){access(p);splay(p);rev(p);} 50 void split(int x,int y){make_root(x);access(y);splay(y);} 51 void link(int x,int y){make_root(x);f[x]=y;up(y);} 52 void cut(int x,int y){split(x,y);f[x]=c[y][0]=0;up(y);} 53 struct edge{ 54 int a,b,l,num; 55 friend bool operator<(edge a,edge b){return a.l>b.l;} 56 }e[1000005]; 57 priority_queue<edge>qu; 58 int fa[100005]; 59 int find(int k){return fa[k]==k?k:fa[k]=find(fa[k]);} 60 void Kruscal(){ 61 for(int i=1;i<=n;++i)fa[i]=i; 62 for(int i=1;i<=m;++i)if(!lck[n+i])qu.push((edge){A[i],B[i],V[i],n+i}); 63 while(!qu.empty()){ 64 int a=qu.top().a,b=qu.top().b,v=qu.top().l,num=qu.top().num;qu.pop(); 65 if(find(a)!=find(b))fa[fa[a]]=fa[b],link(a,num),link(num,b); 66 } 67 } 68 int main(){ 69 scanf("%d%d%d",&n,&m,&q); 70 for(int i=1;i<=m;++i)read(A[i]),read(B[i]),read(V[i]),mm[make_pair(A[i],B[i])]=n+i,v[n+i]=V[i]; 71 for(int i=1;i<=q;++i)read(opt[i]),read(x[i]),read(y[i]),opt[i]--; 72 for(int i=1;i<=q;++i)if(opt[i])lck[mm[make_pair(x[i],y[i])]]=1; 73 Kruscal(); 74 for(int i=q;i;--i) 75 if(opt[i]){ 76 split(x[i],y[i]);int nmx=mx[y[i]],tbc=mxp[y[i]],obj=mm[make_pair(x[i],y[i])]; 77 if(nmx<=V[obj-n])continue; 78 cut(tbc,A[tbc-n]);cut(tbc,B[tbc-n]); 79 link(obj,x[i]);link(obj,y[i]); 80 }else split(x[i],y[i]),ans[i]=mx[y[i]]; 81 for(int i=1;i<=q;++i)if(!opt[i])printf("%d\n",ans[i]); 82 }