由于题目有删除操作，所以我们不妨倒叙枚举，把删边变成加边。某人还起了个好听的名字叫“时光倒流”……
之后用动态树维护一下动态最小生成树就行了，每加入一条边就用动态树树找出两点见最长边，比较大小看是否能替换就行了。
这里还有一个小技巧，就是二分边标号来找出每个询问所对应的边的标号。
24700ms 刚好卡时。
/************************************************************** Problem: 2594 User: vermouth Language: C++ Result: Accepted Time:24700 ms Memory:77040 kb ****************************************************************/ #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn=1001000; int fa[maxn*2],ch[maxn*2][2],n,m; int mx[maxn*2],val[maxn*2],s[maxn],f[101000],cnt; bool rev[maxn*2]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int getf(int x) { if(f[x]==x) return x; else return f[x]=getf(f[x]); } struct edge { int u,v,w,id,f,ans; bool d; }; edge T[maxn],q[110000]; bool cmp(edge i,edge j) { return i.w<j.w; } bool cmp1(edge i,edge j) { if(i.u==j.u) return i.v<j.v; return i.u<j.u; } bool cmp2(edge i,edge j) { return i.id<j.id; } void update(int x) { int l=ch[x][0],r=ch[x][1]; mx[x]=x; if(val[mx[x]]<val[mx[l]]) mx[x]=mx[l]; if(val[mx[x]]<val[mx[r]]) mx[x]=mx[r]; } void pushdown(int x) { if(rev[x]) { rev[x]^=1;rev[ch[x][0]]^=1;rev[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]); } } bool isroot(int x) { return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x; } void rotate(int x) { int y=fa[x],z=fa[y],l=ch[y][1]==x,r=l^1; if(!isroot(y)) ch[z][ch[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[ch[x][r]]=y; ch[y][l]=ch[x][r];ch[x][r]=y; update(y);update(x); } void Splay(int x) { int top=0;s[++top]=x; for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i]; for(int i=top;i;i--) pushdown(s[i]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) { if(ch[y][0]==x^ch[z][0]==y) rotate(x); else rotate(y); } rotate(x); } } void access(int x) { int t=0; while(x) { Splay(x);ch[x][1]=t;update(x);t=x;x=fa[x]; } } void reverse(int x) { access(x);Splay(x);rev[x]^=1; } void link(int x,int y) { reverse(x);fa[x]=y; } void cut(int x,int y) { access(x);reverse(y);Splay(y);ch[y][0]=fa[x]=0; update(x); } int query(int x,int y) { reverse(y);access(x);Splay(x);return mx[x]; } int findkey(int u,int v) { int l=1,r=m; while(l<=r) { int mid=(l+r)>>1; if(T[mid].u<u||(T[mid].u==u&&T[mid].v<v))l=mid+1; else if(T[mid].u==u&&T[mid].v==v)return mid; else r=mid-1; } } int Q,x,y; int main() { scanf("%d%d%d",&n,&m,&Q); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { T[i].u=read();T[i].v=read();T[i].w=read(); if(T[i].u>T[i].v) swap(T[i].u,T[i].v); } sort(T+1,T+1+m,cmp); for(int i=1;i<=m;i++) { T[i].id=i; val[i+n]=T[i].w; mx[i+n]=i+n; } sort(T+1,T+1+m,cmp1); for(int i=1;i<=Q;i++) { q[i].f=read();q[i].u=read();q[i].v=read(); if(q[i].f==2) { if(q[i].u>q[i].v) swap(q[i].u,q[i].v); int t=findkey(q[i].u,q[i].v); T[t].d=1;q[i].id=T[t].id; } } sort(T+1,T+1+m,cmp2); cnt=n; for(int i=1;i<=m;i++) if(!T[i].d) { int u=T[i].u,v=T[i].v,x=getf(u),y=getf(v); if(x!=y) { f[x]=y; link(u,i+n);link(v,i+n); cnt--; } if(cnt==1) break; } for(int i=Q;i>=1;i--) { if(q[i].f==1) { q[i].ans=val[query(q[i].u,q[i].v)]; } else { int u=q[i].u,v=q[i].v,k=q[i].id; int t=query(u,v); if(T[k].w<val[t]) { cut(T[t-n].u,t);cut(T[t-n].v,t); link(u,k+n);link(v,k+n); } } } for(int i=1;i<=Q;i++) if(q[i].f==1) printf("%d\n",q[i].ans); return 0; } /* 4 4 4 1 2 2 2 3 3 3 4 2 1 4 2 1 1 4 2 1 4 1 1 4 1 1 4 */