P4172 [WC2006]水管局长
too_later
·
·
个人记录
题意
维护一个图，支持：
思路
看到断开就是 LCT 了。
接下来就是套路了。
因为短边操作很难维护，考虑离散化加边操作。
维护一个下标 ma。
如果一条边已经在一个环上了，而且环上有一条边权大于当前边权，那么替换。
询问的话就 split 再 query。
```cpp
#include<bits/stdc++.h>
#define I inline
#define ls ch[p][0]
#define rs ch[p][1]
#define chk printf("CaO ")
using namespace std;
const int N = 1000005;
int n,m,q,top,ans[N],x,y,z,xx[N],yy[N],lne[1005][1005],dis[1005][1005];
int op[N],X[N],Y[N],st[N],f[N],ch[N][2],val[N],ma[N],tag[N];
I void down(int p){
if(!tag[p])return;
ls^=rs^=ls^=rs;tag[ls]^=1,tag[rs]^=!(tag[p]=0);
} I void up(int p){
down(ls),down(rs);ma[p]=p;
if(ls)if(val[ma[ls]]>val[ma[p]])ma[p]=ma[ls];
if(rs)if(val[ma[rs]]>val[ma[p]])ma[p]=ma[rs];
} I int get(int p){return p==ch[f[p]][1]; }
I int isroot(int p){return p!=ch[f[p]][0]&&p!=ch[f[p]][1];}
I void rotate(int x){
int y=f[x],z=f[y],k=get(x);if(!isroot(y))ch[z][ch[z][1]==y]=x;
f[ch[y][k]=ch[x][!k]]=y,f[ch[x][!k]=y]=x,f[x]=z,up(y),up(x);if(z)up(z);
}
I void splay(int x){
int i=x;st[top=1]=i;while(!isroot(i))st[++top]=i=f[i];
while(top)down(st[top--]);
for(int fa;fa=f[x],!isroot(x);rotate(x))
if(!isroot(fa))rotate(get(fa)==get(x)?fa:x);
}
I void access(int p){
for(int q=0;p;p=f[q=p])splay(p),rs=q,up(p);
}
I void makeroot(int p){
access(p),splay(p),tag[p]^=1;
}
I void split(int x,int y){
makeroot(x),access(y),splay(y);
}
I int findroot(int p){
access(p),splay(p);down(p);while(ls)p=ls,down(p);return p;
}
I void link(int x,int y){
makeroot(x);f[x]=y;
}
I void cut(int x,int y){
split(x,y);
ch[y][0]=f[x]=0;
up(y);
}
map<int, map<int, int> > mp;
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),mp[xx[i]=x][yy[i]=y]=mp[y][x]=1,
val[i+n]=z,up(i+n),lne[x][y]=lne[y][x]=i,dis[x][y]=dis[y][x]=z;
for(int i=1;i<=q;i++)
scanf("%d%d%d",&op[i],&X[i],&Y[i]),(op[i]==2?mp[X[i]][Y[i]]=mp[Y[i]][X[i]]=0:0);
for(map< int , map< int , int > > :: iterator it1=mp.begin();it1!=mp.end();it1++)
for(map<int,int> :: iterator it2=it1->second.begin();it2!=it1->second.end();it2++){
if(!(it2->second))continue;mp[y=it2->first][x=it1->first]=0;
int i=lne[x][y];
if(findroot(x)!=findroot(y))link(x,i+n),link(i+n,y);
else{
split(x,y);
int mi=ma[y];
if(val[mi]<=dis[x][y])continue;
cut(xx[mi-n],mi);
cut(mi,yy[mi-n]);
link(x,i+n);
link(i+n,y);
}
}
for(;q;q--){
if(op[q]==1){
split(X[q],Y[q]);
ans[++ans[0]]=val[ma[Y[q]]];
} else {
int i=lne[X[q]][Y[q]];
split(X[q],Y[q]);
if(val[ma[Y[q]]]<=dis[X[q]][Y[q]])continue;
int mi=ma[Y[q]];
cut(xx[mi-n],mi);
cut(mi,yy[mi-n]);
link(X[q],i+n);
link(i+n,Y[q]);
}
}
for(int i=ans[0];i;i--)printf("%d\n",ans[i]);
return 0;
}
```