【题解】

　　我们把操作倒过来做，就变成了加边而不是删边。于是用LCT维护动态加边的最小生成树就好了。同样要注意把边权变为点权。

　　

1 #include
      
         2 #include
       
          3 #define N 200010  4 #define rg register  5 #define ls (c[u][0])  6 #define rs (c[u][1])  7 using namespace std;  8 int n,m,q,top,tot;  9 int f[N],fa[N],c[N][2],rev[N],mx[N],pos[N],val[N],st[N],ans[N],num[1001][1001]; 10 bool bro[1001][1001]; 11 struct edge{ 12     int u,v,dis; 13 }e[N]; 14 struct question{ 15     int opt,x,y; 16 }que[N]; 17 inline int read(){ 18     int k=0,f=1; char c=getchar(); 19     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 20     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 21     return k*f; 22 } 23 inline int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);} 24 inline bool cmp(edge a,edge b){
    return a.dis
        
         y?x:y;} 26 inline bool isroot(int u){
    return c[fa[u]][0]!=u&&c[fa[u]][1]!=u;} 27 inline bool which(int u){
    return c[fa[u]][1]==u;} 28 inline void pushup(int u){ 29     pos[u]=u; mx[u]=val[u]; 30     if(mx[ls]>mx[u]) pos[u]=pos[ls],mx[u]=mx[ls]; 31     if(mx[rs]>mx[u]) pos[u]=pos[rs],mx[u]=mx[rs]; 32 } 33 inline void pushdown(int u){ 34     rev[u]=0; rev[ls]^=1; rev[rs]^=1; swap(ls,rs); 35 } 36 inline void rotate(int u){ 37     int f=fa[u],g=fa[f],wh=which(u); 38     if(!isroot(f)) c[g][which(f)]=u; 39     fa[u]=g; fa[f]=u; fa[c[u][wh^1]]=f; 40     c[f][wh]=c[u][wh^1]; c[u][wh^1]=f; 41     pushup(f); pushup(u); 42 } 43 inline void splay(int u){ 44     st[top=1]=u; 45     for(rg int i=u;!isroot(i);i=fa[i]) st[++top]=fa[i]; 46     for(rg int i=top;i;i--) if(rev[st[i]]) pushdown(st[i]); 47     while(!isroot(u)){ 48         if(!isroot(fa[u])) rotate(which(u)==which(fa[u])?fa[u]:u); 49         rotate(u); 50     } 51 } 52 inline void access(int u){ 53     for(rg int s=0;u;s=u,u=fa[u]) splay(u),c[u][1]=s,pushup(u); 54 } 55 inline void makeroot(int u){access(u); splay(u); rev[u]^=1;} 56 inline int findroot(int u){ 57     access(u); splay(u); 58     while(ls) u=ls; return u; 59 }  60 inline void split(int x,int y){makeroot(x); access(y); splay(y);} 61 inline void link(int x,int y){makeroot(x); fa[x]=y;} 62 inline void cut(int x,int y){ 63     split(x,y); int t=c[y][0]; 64     if(t==x&&!c[t][1]) fa[x]=0,c[y][0]=0; 65     else{ 66         while(c[t][1]) t=c[t][1]; 67         if(t==x) fa[x]=0,c[y][0]=0; 68     } 69 } 70 inline void build(){ 71     sort(e+1,e+1+m,cmp); 72     for(rg int i=1;i<=n;i++) f[i]=i; 73     for(rg int i=1;i<=m;i++){ 74         val[i+n]=e[i].dis; 75         num[e[i].u][e[i].v]=num[e[i].v][e[i].u]=i; 76     } 77     int cnt=0; 78     for(rg int i=1;i<=m;i++){ 79         int u=e[i].u,v=e[i].v; 80         if(bro[u][v]) continue; 81         if(find(u)!=find(v)){ 82             cnt++; link(u,i+n); link(v,i+n); 83             f[find(u)]=find(v); 84         } 85         if(cnt>=n-1) break; 86     } 87 } 88 inline void work(){ 89     for(rg int i=q;i;i--){ 90         int opt=que[i].opt,x=que[i].x,y=que[i].y; 91         if(opt==1){ 92             split(x,y); ans[++tot]=mx[y]; 93         } 94         else{ 95             int ne=num[x][y]; 96             split(x,y); 97             if(e[ne].dis