题目
做法
是否看作水题，其实就在于是否想到了离线：对于动态删除边维护最大权看上去束手无策，其实转换一下倒序处理操作就是动态添边维护最大权了
要是不知道动态添边维护最大权，看这题做法
My complete code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef int LL;
const LL maxn=1e6,B=(1<<17);
inline LL Read(){
LL x(0),f(1);char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
struct code{
LL x,y;
}uv[maxn];
struct node{
LL op,x,y;
}q[maxn];
LL n,m,Q,tot;
LL son[maxn][2],fa[maxn],sum[maxn],mx[maxn],sta[maxn],edge[maxn],r[maxn],dis[1200][1200],id[1200][1200],ans[maxn],f[maxn];
inline void Update(LL x){
sum[x]=edge[x]+sum[son[x][0]]+sum[son[x][1]];
mx[x]=x;
if(edge[mx[x]]<edge[mx[son[x][0]]]) mx[x]=mx[son[x][0]];
if(edge[mx[x]]<edge[mx[son[x][1]]]) mx[x]=mx[son[x][1]];
}
inline bool Notroot(LL x){
return son[fa[x]][0]==x||son[fa[x]][1]==x;
}
inline void Pushr(LL x){
swap(son[x][0],son[x][1]),r[x]^=1;
}
inline void Pushdown(LL x){
if(r[x]){
if(son[x][0]) Pushr(son[x][0]);
if(son[x][1]) Pushr(son[x][1]);
r[x]=0;
}
}
inline void Rotate(LL x){
LL y(fa[x]),z(fa[y]),lz(son[y][1]==x);
if(Notroot(y)) son[z][son[z][1]==y]=x; fa[x]=z;
son[y][lz]=son[x][lz^1];
if(son[y][lz]) fa[son[y][lz]]=y;
son[x][lz^1]=y,fa[y]=x;
Update(y),Update(x);
}
inline void Splay(LL x){
LL y(x),top(0);sta[++top]=y;
while(Notroot(y)) sta[++top]=y=fa[y];
while(top) Pushdown(sta[top--]);
while(Notroot(x)){
y=fa[x];
if(Notroot(y)){
LL z(fa[y]);
if(((son[z][1]==y)^(son[y][1]==x))==0) Rotate(y);
else Rotate(x);
}Rotate(x);
}
}
inline void Access(LL x){
for(LL y=0;x;y=x,x=fa[x])
Splay(x),son[x][1]=y,Update(x);
}
inline void Makeroot(LL x){
Access(x),Splay(x),Pushr(x);
}
inline void Split(LL x,LL y){
Makeroot(x),Access(y),Splay(y);
}
inline void Link(LL x,LL u,LL v){
Makeroot(u),Makeroot(v);
fa[u]=x,fa[x]=v;
}
inline void Delet(LL x,LL u,LL v){
Split(u,v),Splay(x);
fa[u]=fa[v]=son[x][0]=son[x][1]=0;
}
LL Get_fa(LL x){
return f[x]=(f[x]==x?x:Get_fa(f[x]));
}
int main(){
n=Read(),m=Read(),Q=Read();
for(LL i=1;i<=n;++i) f[i|B]=i|B;
for(LL i=1;i<=m;++i){
LL u(Read()),v(Read()),w(Read());
dis[u][v]=dis[v][u]=w;
uv[i]=(code){v|B,u|B};
id[u][v]=id[v][u]=i;
edge[i]=w;
}
for(LL i=1;i<=Q;++i){
q[i]=(node){Read(),Read(),Read()};
if(q[i].op==2)
dis[q[i].x][q[i].y]=dis[q[i].y][q[i].x]=0;
else ++tot;
}
for(LL i=1;i<=n;++i)
for(LL j=i+1;j<=n;++j)
if(dis[i][j]){
LL x(id[i][j]),u(i|B),v(j|B);
if(Get_fa(u)==Get_fa(v)){
Split(u,v);
if(edge[mx[v]]>edge[x]){
Delet(mx[v],uv[mx[v]].x,uv[mx[v]].y);
Link(x,u,v);
}
}else{
Link(id[i][j],u,v);
f[Get_fa(u)]=Get_fa(v);
}
}
LL tmp(tot);
for(LL i=Q;i>=1;--i){
LL op(q[i].op),u(q[i].x),v(q[i].y),x(id[u][v]);
u|=B,v|=B;
if(op==1){
Split(u,v);
ans[tot--]=edge[mx[v]];
}else{
if(Get_fa(u)==Get_fa(v)){
Split(u,v);
if(edge[mx[v]]>edge[x]){
Delet(mx[v],uv[mx[v]].x,uv[mx[v]].y);
Link(x,u,v);
}
}else{
Link(x,u,v);
f[Get_fa(u)]=Get_fa(v);
}
}
}
for(LL i=1;i<=tmp;++i) printf("%d
",ans[i]);
return 0;
}