题解 P4172 【[WC2006]水管局长】

**我的博客：[传送门](https://www.wjyyy.top/2956.html)** ## 题解： 这个题要维护的是一个图而不是一棵树，看似不能用LCT写。但是这是LCT的一个用法——维护生成树。 --- 因为本题要求出**路径上的最大值**，可能会想到[货车运输](https://www.luogu.org/problemnew/show/P1967)的一个贪心，并维护生成树。然而还需要动态删边，万一删掉了生成树上的边，总不能再做一遍生成树吧？ 但是这个题只有删边，因此过程是**单调的**，因此把它倒过来就是加边。加边理论上就好做一些了。 因为保证了“任何时候我们考虑的水管网络都是连通的”，所以先把图删到最后，不做任何查询操作，这一点又有点像[航线规划](https://www.luogu.org/problemnew/show/P2542)一题了（这题以前是用[树剖水过去的](https://www.wjyyy.top/895.html)，也是先把边删完）。 此时我们求出残余图上的最小生成树，那么任意两点之间只要沿着这棵MST上走，就是最优的，这是一个贪心。 拿LCT维护这棵生成树，splay上的点维护的是区间最大值，本质上是一条链的最大权值。 之后考虑加边，也就是动态的MST了，顺着上面贪心的思路想，如果在树上加入一条边，就会形成一个环。此时从任意一点进入环，从另一点出环，可以从环上两个方向走，那么最优解总可以避开最长的一条边。  比如说从$E$到$D$，最优的路径是$E-C-A-B-D$，路径最大值为$7$，而$E-F-D$最大值为$8$。那么$D-F$这条边可以删掉，原因是最优解总不必经过这条边。 那么假设$E-F$这条边是新加进来的，原来的图是这样（“环”上的点还连接有其他的边，但保证是一棵树）  我们现在只关注这个“环”，先用`split(E,F)`把$E-F$这条**链**的信息提取出来。此时可以查询出链上的最大权值$8$，与即将加入的$3$进行比较。发现$3<8$。说明这个环上可以删掉权值最大的边来保证最优，那么在平衡树上“二分”出这条边，来删除它。如果即将加入的边权比整条链上的最大值还大，那么直接忽略这个操作。 上面提到的“二分”实际上是在平衡树上查找。如果发现根节点的值就是所要的值，就返回根节点，否则哪棵子树中有这个最大值，就进哪棵子树，这一步复杂度均摊$O(\log n)$。 查询的时候直接`split()`然后查询链的信息就好了。 还有一个重要的是如何维护边，这时不能像树剖那样维护到父亲的边了。因为LCT比较灵活，所以考虑用一个点来代表一条边。比如说我要连接原图上的$1,2$两点，把这条边命名为$A$（$A$在程序中还是会用数字来表示的），权值为$4$。  就把$1,2$与$A$分别连接起来。$A$在整张图中始终只与$1,2$这两个点相连，边权在LCT上表示为点权。原图上的点点权为$0$（如果要求最小值原图上的点应该设为$+\infty$）。 然后倒序**加边**，再把答案倒过来输出就可以了。 ## Code： 代码并没有什么注释，希望dalao们把思想理解后做题 ```cpp #include<cstdio> #include<cstring> #include<algorithm> #define ls ch[0][k] #define rs ch[1][k] #define which(k) (ch[1][fa[k]]==k) #define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k) using std::max; int ch[2][120000],fa[120000]; int key[120000],sum[120000],lazy[120000]; void maintain(int k) { sum[k]=max(max(sum[ls],key[k]),sum[rs]); } void pushdown(int k) { if(lazy[k]) { int tmp=ls; ls=rs; rs=tmp; lazy[k]=0; lazy[ls]^=1; lazy[rs]^=1; } } void Rotate(int k) { int y=fa[k]; if(!isroot(y)) ch[which(y)][fa[y]]=k; bool d=which(k); fa[k]=fa[y]; fa[y]=k; ch[d][y]=ch[!d][k]; fa[ch[d][y]]=y; ch[!d][k]=y; maintain(y); maintain(k); } int stk[120000],tp=0; void splay(int k) { int x=k; while(!isroot(x)) { stk[++tp]=x; x=fa[x]; } stk[++tp]=x; while(tp) pushdown(stk[tp--]); while(!isroot(k)) { int y=fa[k]; if(!isroot(y)) Rotate(which(k)^which(y)?k:y); Rotate(k); } } void access(int k) { for(int x=k,y=0;x;y=x,x=fa[x]) { splay(x); ch[1][x]=y; maintain(x); } } void makeroot(int k) { access(k); splay(k); lazy[k]^=1; } void split(int x,int y) { makeroot(x); access(y); splay(y); } void link(int x,int y) { makeroot(x); fa[x]=y; } void cut(int x,int y) { makeroot(x); access(y); splay(y); fa[x]=ch[0][y]=0; } int Find(int k,int x) { if(key[k]==x) return k; if(sum[ls]==x) return Find(ls,x); return Find(rs,x); } int f[1010][1010],U[101000],V[101000],op[101000]; int n,m,q; struct edge { int x,y,v,ava; edge(){ava=1;} friend bool operator <(edge a,edge b) { return a.v<b.v; } }e[101000]; int s[1010]; int Find(int x) { if(s[x]!=x) return s[x]=Find(s[x]); return x; } void Union(int x,int y) { s[Find(x)]=Find(y); } void mst() { for(int i=1;i<=n;++i) s[i]=i; for(int i=1;i<=m;++i) if(e[i].ava&&Find(e[i].x)!=Find(e[i].y)) { Union(e[i].x,e[i].y); link(e[i].x,n+i); link(e[i].y,n+i); } } int ans[101000]; int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v); std::sort(e+1,e+1+m); for(int i=1;i<=m;++i) { f[e[i].x][e[i].y]=f[e[i].y][e[i].x]=i; key[n+i]=e[i].v; } for(int i=1;i<=q;++i) { scanf("%d%d%d",&op[i],&U[i],&V[i]); if(op[i]==2) e[f[U[i]][V[i]]].ava=0; } mst(); int cnt=0; for(int i=q;i>=1;--i) { split(U[i],V[i]);//V[i]是根 if(op[i]==1) ans[++cnt]=sum[V[i]]; else { int t=Find(V[i],sum[V[i]]); if(key[f[U[i]][V[i]]+n]<sum[V[i]]) { cut(e[t-n].x,t); cut(e[t-n].y,t); link(U[i],f[U[i]][V[i]]+n); link(V[i],f[U[i]][V[i]]+n); } } } for(int i=cnt;i>=1;--i) printf("%d\n",ans[i]); return 0; } ```