欢迎访问~原文出处——

题意概括

　　N个点的图，M条带权边。（N<=100000,M<=1000000）

　　有Q次操作(Q<=100000)

　　操作有两个类型：

　　1.问节点x到y的路径中边的最大权值。

　　2.删除某一条边

　　操作过程中保证图连通

题解

　　我们发现很难做。

　　能够1A也是我运气好。

　　我们发现顺着做貌似很难，要找到边，然后删掉……

　　这题是LCT的，显然不会在图上做。

　　看了看网上的题解，懂了。

　　倒着来，把删边看作加边。

　　假如没有删边或者加边的操作，那么有用的边一定是最小生成树上的。

　　换句话说就是a~b中路径的最大权值最小的边一定在当前最小生成树上。

　　于是我们倒着维护一棵最小生成树。

　　每次加入一条边，连接x和y，权值为z，我们要找到x和y的路径中权值最大的边。

　　然后把他删掉，再添入当前边（当然这个权值最大的可能是他自己，那么什么都不干了）。

　　这个贪心的思想应该不用讲了吧。

　　现在是关键是怎么做。

　　我们考虑用LCT来维护。

　　但是LCT只可以维护点权，很难做到维护边权。

　　所以我们化边为点。

　　我们把每一条边看作一个点。

　　然后比如说第k条边连接了x和y，那么连上第k条边的时候，我们就分别link(x,k)和link(y,k)

　　然后就达到了连接点的同样的效果。

　　那么，再写一个LCT维护一下最大值就可以了。

　　这里有一个小技巧，就是记录最大值编号。

　　还有一个查询边的问题，那么我们可以给边按照节点排个序，然后二分查找即可。

　　这个可以事先处理好。

　　详见代码

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=100005,M=1000005,S=N+M;bool isd(char ch){	return '0'<=ch&&ch<='9';}void read(int &x){	x=0;	char ch=getchar();	while (!isd(ch))		ch=getchar();	while (isd(ch))		x=x*10+ch-48,ch=getchar();}int n,m,Q,s;int fa[S],son[S][2],rev[S],val[S],Max[S];int ans[N];struct Three{	int x,y,z,flag;	void Read(int flag){		read(x),read(y),read(z);		if (flag&&x>y)			swap(x,y);		flag=0;	}}e[M],q[N];bool cmp1(Three a,Three b){	return (a.x==b.x&&a.y
          
           
            b) swap(a,b); int L=1,R=m,mid; while (L<=R){ mid=(L+R)>>1; if (e[mid].x==a&&e[mid].y==b) return mid; if ((e[mid].x==a&&e[mid].y
            
             
              e[RMax].z?LMax:RMax; Max[x]=e[val[x]].z>e[Max[x]].z?val[x]:Max[x];}void pushdown(int x){ if (rev[x]){ rev[x]=0; rev[son[x][0]]^=1; rev[son[x][1]]^=1; swap(son[x][0],son[x][1]); }}void pushadd(int x){ if (!isroot(x)) pushadd(fa[x]); pushdown(x);}int wson(int x){ return son[fa[x]][1]==x;}void rotate(int x){ if (isroot(x)) return; int y=fa[x],z=fa[y],L=wson(x),R=L^1; if (!isroot(y)) son[z][wson(y)]=x; fa[x]=z,fa[y]=x,fa[son[x][R]]=y; son[y][L]=son[x][R],son[x][R]=y; pushup(y),pushup(x);}void splay(int x){ pushadd(x); for (int y=fa[x];!isroot(x);rotate(x),y=fa[x]) if (!isroot(y)) rotate(wson(x)==wson(y)?y:x);}void access(int x){ int t=0; while (x){ splay(x); son[x][1]=t; pushup(x); t=x; x=fa[x]; }}void rever(int x){ access(x); splay(x); rev[x]^=1;}void link(int x,int y){ rever(x); fa[x]=y;}void split(int x,int y){//让y做x的左儿子 rever(y); access(x); splay(x);}void cut(int x,int y){ split(y,x); fa[x]=son[y][0]=0;}int find(int x){ access(x); splay(x); while (1){ pushdown(x); if (son[x][0]) x=son[x][0]; else break; } return x;}int main(){ read(n),read(m),read(Q); for (int i=1;i<=m;i++) e[i].Read(1); for (int i=1;i<=Q;i++) q[i].Read(0); sort(e+1,e+m+1,cmp1); for (int i=1;i<=Q;i++) if (q[i].x==2) e[search(q[i].y,q[i].z)].flag=i; sort(e+1,e+m+1,cmp2); for (int i=1;i<=m;i++) if (e[i].flag) q[e[i].flag].flag=i; s=n+m; for (int i=1;i<=s;i++) clear(i,i<=n?0:(i-n)); e[0].z=0; for (int i=1,j=1;i<=m&&j
              
               =1;i--){ int k=q[i].x,x=q[i].y,y=q[i].z; if (k==1){ split(x,y); ans[i]=e[Max[x]].z; } if (k==2){ split(x,y); int cE=Max[x],aE=q[i].flag; if (e[cE].z>e[aE].z){ cut(e[cE].x,cE+n); cut(e[cE].y,cE+n); link(e[aE].x,aE+n); link(e[aE].y,aE+n); } } } for (int i=1;i<=Q;i++) if (q[i].x==1) printf("%d\n",ans[i]); return 0;}