[WC2006] 水管局长

显然，这道题需要维护一棵最小生成树，支持动态删边，查询链上最大值。查询链上最大值可以倍增维护，但是本题 \(n\) 较小，直接暴力往上跳也是可过的。
接下来就是如何动态维护最小生成树的问题了。对于一般图的最小生成树求解，我们有 \(O(m\log m)\) 的 Kruskal 算法和 \(O(n^2)\) 的 Prim 算法。然而这两种方法都是静态的，无法支持动态加（删）边，是否有方法能高效地动态维护最小生成树呢？
题解里全都是 LCT，可我不会啊？于是开发出了一些新方法。

方法一

数据范围中有一个特别显眼的地方：宣布报废的水管不超过 \(5 \times 10^3\) 条。那我们就考虑暴力重构，设重构次数为 \(T\)，显然 \(O(Tm\log m)\) 的复杂度不可接受，但是我们可以想到：每次重构都排序是不必要的，可以一开始对所有边排序，后续每次 Kruskal 时只 \(O(m)\) 遍历每条边，检查当前边是否被删除，若被删除直接跳过即可。单次重构时间复杂度 \(\Theta(n+n\alpha(n)+m)\)，理论上已经可过了，但是由于常数较大最终未能通过。

方法二

既然正着过不去，我们考虑将整个过程倒着来，改为加边操作，考虑加边的过程：先将 \((u,v)\) 加入到最小生成树中，变成一棵基环树，然后断掉环内边权最大的边即可。换成更好维护的方式：查询链 \(u,v\) 上的最大值，若其小于 \(w(u,v)\)，则不将其加入最小生成树，反之则加入，并删除原来链 \(u,v\) 上的最大值所对的边。高效删边可以通过将邻接表的 std::vector 换成 std::set 实现。然后再 dfs 一遍重构父子关系。这样，我们就把单次重构的复杂度降为了 \(\Theta(n+\log n)\)。

code

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
template<typename T>
inline void read(T &x){bool f=0;x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=1e3+10,M=1e5+10;
struct Que{int op,u,v;}ask[M];
struct Edge{int v,w;bool operator<(const Edge &x)const{return v<x.v;}
};
set<Edge> g[N];
int n,m,q,fa[N],val[N],dep[N];
int w[N][N],boss[N],ans[M];
struct edge{int u,v,t;bool operator<(const edge &x)const{return w[u][v]<w[x.u][x.v];}
}e[M];
bool del[N][N];
int find(int x){return boss[x]==x?x:boss[x]=find(boss[x]);}
void dfs(int u,int f){dep[u]=dep[f]+1;for(auto &[v,w]:g[u]){if(v==f) continue;fa[v]=u;val[v]=w;dfs(v,u);}
}
inline void build(){for(int i=1;i<=n;i++) boss[i]=i;int cnt=0;for(int i=1;i<=m;i++){int u=e[i].u,v=e[i].v;if(del[u][v]) continue;int val=w[u][v];u=find(u),v=find(v);if(u==v) continue;boss[u]=v;g[e[i].u].insert({e[i].v,val});g[e[i].v].insert({e[i].u,val});if(++cnt==n-1) break;}dfs(1,0);
}
typedef pair<int,edge> pr;
inline pr query(int x,int y){pr res={};while(x!=y){if(dep[x]<dep[y]) swap(x,y);if(val[x]>res.first)res={val[x],{x,fa[x]}};x=fa[x];}return res;
}
int main(){read(n,m,q);for(int i=1,t;i<=m;i++){read(e[i].u,e[i].v,t);w[e[i].u][e[i].v]=w[e[i].v][e[i].u]=t;}for(int i=1;i<=q;i++){read(ask[i].op,ask[i].u,ask[i].v);if(ask[i].op==2)del[ask[i].u][ask[i].v]=del[ask[i].v][ask[i].u]=1;}sort(e+1,e+1+m);build();for(int i=q;i;i--){int u=ask[i].u,v=ask[i].v;pr res=query(u,v);if(ask[i].op==1) ans[i]=res.first;else{if(res.first<=w[u][v]) continue;edge old=res.second;g[old.u].erase({old.v,w[old.u][old.v]});g[old.v].erase({old.u,w[old.u][old.v]});g[u].insert({v,w[u][v]});g[v].insert({u,w[u][v]});dfs(1,0);}}for(int i=1;i<=q;i++) if(ans[i]) printf("%d\n",ans[i]);return 0;
}