题解 P4180 【【模板】严格次小生成树[BJWC2010]】
wjyyy
2019-01-07 20:12:14
**给大常数lct选手一个救赎的机会。**
**博客地址：[传送门](https://www.wjyyy.top/3020.html)**
## 题解：
第一眼看上去是一个lct维护生成树的问题。然而没有动态加删边，可能是大材小用。
不过用lct直接维护生成树也有一定的问题。如果我们枚举不在生成树上的边，找环并删除环上边权小于当前边的权值最大的边，也许并不能保证**最小生成树与(严格)次小生成树只相差一对边**。
实际上是可以的。我们用反证法稍微考虑一下最小生成树(MST)与(严格)次小生成树(SST)相差两对边的情况。
_如果MST和SST相差两对边，假设分别为$\{a_1,b_1\},\{a_2,b_2\}$，也就是说$\{a_1,a_2\}$在MST上，$\{b_1,b_2\}$在SST上。那么一定有_
$$a_1+a_2<b_1+b_2\qquad(1)$$
_但是这个不等式可以有多种情况，我们现在已经把$\{a_1,a_2\}$删掉了，还要加回两条边（不为原来的边）使得图重新构成一棵生成树，可以有$\{a_1,b_1\},\{a_1,b_2\},\{a_2,b_2\},\{a_2,b_1\},\{b_1,b_2\}$这五种情况。但是无论如何，$\{b_1,b_2\}$都不会是这五组中最小的。_
_假设$a_1\le a_2,b_1\le b_2$，若$a_1<b_1$，则$\{a_1,b_2\}$一定在次小生成树上了了，若$a_1\ge b_1$，由不等式$(1)$，一定有$a_2<b_2$，那么此时$\{a_2,b_1\}$就最优了。_
_证毕。_
那么此时就考虑查询一条链上小于$x$的最大边权来更新答案。因为lct是用splay做的，所以可以维护链上的最大值和次大值，大致是这样的：
```cpp
void maintain(int k)
{
sum[k]=Max(Max(sum[ls],key[k]),sum[rs]);//维护最大值
ssum[k]=0;//次大值
ssum[k]=(sum[ls]<sum[k]&&sum[ls]>ssum[k])?sum[ls]:ssum[k];//次大值只可能在这四种中出现
ssum[k]=(key[k]<sum[k]&&key[k]>ssum[k])?key[k]:ssum[k];
ssum[k]=(ssum[ls]<sum[k]&&ssum[ls]>ssum[k])?ssum[ls]:ssum[k];
ssum[k]=(ssum[rs]<sum[k]&&ssum[rs]>ssum[k])?ssum[rs]:ssum[k];
}
```
常数是原来的$3$倍多。轻而易举TLE。~~因此如果不是要练LCT还是建议大家写倍增/树剖。~~
不过我们可以提取出来这条链然后dfs这棵子splay，带入参数$x$，找到小于$x$的最大边权。既然我们已经维护了子树最大值，就可以**剪枝**，对，就是剪枝。如果子树最大值小于$x$了，直接用最大值更新答案并返回，否则继续dfs。
这种操作的最坏复杂度是$O(nm)$的，一条构造过的链应该可以卡得掉。不过数据强度不是很大，剪枝效果比较好，O2最慢的点也只跑了709ms。
## Code：
```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)
int read()
{
char ch=getchar();
int x=0;
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
int Max(int x,int y)
{
return x>y?x:y;
}
int ch[2][401000],fa[401000];
int key[401000],sum[401000],lazy[401000];
void pushdown(int k)
{
if(lazy[k])
{
lazy[k]=0;
int tmp=ls;
ls=rs;
rs=tmp;
lazy[ls]^=1;
lazy[rs]^=1;
}
}
void maintain(int k)
{
sum[k]=Max(Max(sum[ls],key[k]),sum[rs]);
}
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[401000],tp=0;
void splay(int k)
{
while(!isroot(k))
{
stk[++tp]=k;
k=fa[k];
}
stk[++tp]=k;
int qaq=fa[k];
while(tp)
pushdown(stk[tp--]);
k=stk[1];
while(fa[k]!=qaq)
{
int y=fa[k];
if(!isroot(y))
Rotate(which(k)^which(y)?k:y);
Rotate(k);
}
}
void access(int k)
{
for(register 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;
}
int getroot(int k)
{
access(k);
splay(k);
while(ls)
k=ls;
return k;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void link(int x,int y)
{
makeroot(x);
fa[x]=y;
}
int Find(int k,int x)//在splay中找小于x的最大值
{
int tmp=0;
if(key[k]<x)//先比较当前节点
tmp=key[k];
if(sum[ls]<x)//决策进不进入左儿子
tmp=tmp>sum[ls]?tmp:sum[ls];
else
{
int y=Find(ls,x);
tmp=tmp>y?tmp:y;
}
if(sum[rs]<x)//右儿子
tmp=tmp>sum[rs]?tmp:sum[rs];
else
{
int y=Find(rs,x);
tmp=tmp>y?tmp:y;
}
return tmp;
}
struct edge
{
int x,y,w;
friend bool operator <(edge a,edge b)
{
return a.w<b.w;
}
}e[300100];
bool used[300100];
int main()
{
int n,m;
long long Sum=0,ans=1e18;
n=read();
m=read();
for(int i=1;i<=m;++i)
{
e[i].x=read();
e[i].y=read();
e[i].w=read();
}
std::sort(e+1,e+1+m);
for(int i=1;i<=m;++i)
{
key[n+i]=sum[n+i]=e[i].w;
makeroot(e[i].x);
if(getroot(e[i].y)!=e[i].x)
{
used[i]=1;
link(e[i].x,n+i);
link(e[i].y,n+i);
Sum+=e[i].w;
}
}
for(int i=1;i<=m;++i)
if(!used[i])
{
split(e[i].x,e[i].y);
int t=Find(e[i].y,e[i].w);//不超过e[i].w
ans=ans<Sum+key[n+i]-t?ans:Sum+key[n+i]-t;
}
printf("%lld\n",ans);
return 0;
}
```