题解P4180【严格次小生成树】
lengxinjy
·
·
题解
看到写LCT的人比较少啊……就来一波LCT吧
LCT十分擅长解决树的动态加边、删边问题以及与生成树有关的问题，比如此题。
现在假设我们已经求出了一张图的最小生成树，那么我们应该如何调整才能求出严格次小生成树呢？
我们注意到，一定存在一棵严格次小生成树，使得这棵次小生成树与最小生成树只有一条边的差别。（至于咋注意到的本蒟蒻也不会）
所以，求出最小生成树后，我们可以枚举每一条不在生成树上的边，来尝试将这条边加入生成树。由于此时生成树的形态已经完整，再加入一条边后，树上必定会形成环，所以我们应该尝试用这条新边e_{now}替换这两点间路径上边权最大的一条边e_{max}（因为原树已经是最小生成树，所以一定有v[e_{now}]\geq v[e_{max}]）。这里需要注意一点，由于可能存在v[e_{now}]= v[e_{max}]的情况，而本题要求的是严格次小生成树，因此当这种情况出现时，我们应该替换的不是e_{max}而是路径上边权严格次小的边e_{max2}。每次尝试后求出权值，最后取所有替换方案权值的最小值即为答案。
到这里，实现方法已经很清楚了。用一棵LCT维护子树的最大值和严格次大值的节点编号mx及mx2，先对所有边按权值排序，求出MST及其权值ans后，枚举每一条非MST边，每次执行split(e[i].u,e[i].v)，那么当前替换后的答案就是ans-v[mx[e[i].v]]+e[i].w或ans-v[mx2[e[i].v]]+e[i].w。更新答案时取\min即可。
这里还有一个小问题，如何维护严格次大值？我们发现，对于一个节点x，设其左右子节点ls和rs，那么能成为mx2[x]的点就只有五种可能:x,mx[ls],mx[rs],mx2[ls],mx2[rs]。逐个判断即可。
```cpp
void update(int x)
{
mx[x]=x;
if(son[0][x]&&v[mx[son[0][x]]]>v[mx[x]])mx2[x]=mx[x],mx[x]=mx[son[0][x]];
else if(son[0][x]&&v[mx[son[0][x]]]>v[mx2[x]]&&v[mx[son[0][x]]]<v[mx[x]])mx2[x]=mx[son[0][x]];
if(son[0][x]&&v[mx2[son[0][x]]]>v[mx2[x]]&&v[mx2[son[0][x]]]<v[mx[x]])mx2[x]=mx2[son[0][x]];
if(son[1][x]&&v[mx[son[1][x]]]>v[mx[x]])mx2[x]=mx[x],mx[x]=mx[son[1][x]];
else if(son[1][x]&&v[mx[son[1][x]]]>v[mx2[x]]&&v[mx[son[1][x]]]<v[mx[x]])mx2[x]=mx[son[1][x]];
if(son[1][x]&&v[mx2[son[1][x]]]>v[mx2[x]]&&v[mx2[son[1][x]]]<v[mx[x]])mx2[x]=mx2[son[1][x]];
}
```
（这里感觉有些繁琐，如果有大佬有更好的方法欢迎提出）
另外还有一个常数优化。我们没有必要先求出最小生成树后再枚举替换的边，而可以直接扫一遍所有的边，用并查集维护点的连通性。若两点不连通，就直接$link$并且将最小生成树的权值$ans++$；若两点已连通，则用上面的方法尝试替换并更新严格次小生成树与最小生成树的权值之差$delta$。最后输出$ans+delta$即可。
如果还是被卡常怎么办？吸氧大法好……
贴代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ff first
#define ss second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int INF=2147483647;
inline int read()
{
int x=0,k=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*k;
}
int fa[400086],son[2][400086],mx[400086],mx2[400086],v[400086],f[100086],n,m,x,y,k,num,cnt,now,ans;
bool r[400086];
struct edge{
int u,v,w;
bool operator<(edge x)const
{
return w<x.w;
}
}e[300086];
bool isroot(int x)
{
return (son[0][fa[x]]!=x)&&(son[1][fa[x]]!=x);
}
void rvers(int x)
{
r[x]^=1;
swap(son[0][x],son[1][x]);
}
void pushdown(int x)
{
if(!r[x])return ;
if(son[0][x])rvers(son[0][x]);
if(son[1][x])rvers(son[1][x]);
r[x]=0;
}
void update(int x)
{
mx[x]=x;
if(son[0][x]&&v[mx[son[0][x]]]>v[mx[x]])mx2[x]=mx[x],mx[x]=mx[son[0][x]];
else if(son[0][x]&&v[mx[son[0][x]]]>v[mx2[x]]&&v[mx[son[0][x]]]<v[mx[x]])mx2[x]=mx[son[0][x]];
if(son[0][x]&&v[mx2[son[0][x]]]>v[mx2[x]]&&v[mx2[son[0][x]]]<v[mx[x]])mx2[x]=mx2[son[0][x]];
if(son[1][x]&&v[mx[son[1][x]]]>v[mx[x]])mx2[x]=mx[x],mx[x]=mx[son[1][x]];
else if(son[1][x]&&v[mx[son[1][x]]]>v[mx2[x]]&&v[mx[son[1][x]]]<v[mx[x]])mx2[x]=mx[son[1][x]];
if(son[1][x]&&v[mx2[son[1][x]]]>v[mx2[x]]&&v[mx2[son[1][x]]]<v[mx[x]])mx2[x]=mx2[son[1][x]];
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
bool t=(son[1][y]==x);
if(!isroot(y))son[son[1][z]==y][z]=x;
fa[x]=z;
fa[y]=x;
son[t][y]=son[!t][x];
son[!t][x]=y;
if(son[t][y])fa[son[t][y]]=y;
update(y);
update(x);
}
void pathdown(int x)
{
if(!isroot(x))pathdown(fa[x]);
pushdown(x);
}
void splay(int x)
{
pathdown(x);
for( ;!isroot(x);rotate(x))
if(!isroot(fa[x]))(son[0][fa[x]]==x)^(son[0][fa[fa[x]]]==fa[x])?rotate(x):rotate(fa[x]);
}
void access(int x)
{
int y=0;
while(x)
{
splay(x);
son[1][x]=y;
update(x);
y=x;
x=fa[x];
}
}
void makeroot(int x)
{
access(x);
splay(x);
rvers(x);
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void link(int x,int y)
{
split(x,y);
fa[x]=y;
}
void cut(int x,int y)
{
split(x,y);
fa[x]=son[0][y]=0;
update(y);
}
int query(int x,int y)
{
split(x,y);
return mx[y];
}
int query2(int x,int y)
{
split(x,y);
return mx2[y];
}
int find(int x)
{
if(x!=f[x])return f[x]=find(f[x]);
return f[x];
}
void merge(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx==fy)return ;
f[fx]=fy;
}
signed main()
{
n=read(),m=read();
rep(i,1,n)f[i]=i;
rep(i,1,m)
{
x=read(),y=read(),k=read();
if(x>y)swap(x,y);
e[i].u=x,e[i].v=y,e[i].w=k;
}
sort(e+1,e+1+m);
int delta=0x7f7f7f7f7f7f7f7f;
rep(i,1,m)
{
x=e[i].u,y=e[i].v,k=e[i].w;
int fx=find(x),fy=find(y);
if(fx==fy)
{
int w=query(x,y),w2=query2(x,y);
if(v[w]<k)delta=min(delta,k-v[w]);
else delta=min(delta,k-v[w2]);
}
else
{
merge(x,y);
v[i+n]=k;
link(x,i+n),link(i+n,y);
ans+=k;
}
}
printf("%lld",ans+delta);
return 0;
}
```