最小生成树

严格次小生成树

模板

前置知识：

• kruskal

• 倍增求 lca

为方便叙述，最小生成树中的 \(n-1\) 边叫做树边，剩余的 \(m-n+1\) 条边叫非树边。

显然，对于已经生成的最小生成树来说，每一条非树边的加入，都会形成一个环。那么再将环上的树边中最大的边删除，就能得到次小生成树的一颗候选树。

令最小生成树大小为 \(minn\)，新加入的非树边权值为 \(new\)，环上的最大树边为 \(max\)，那么候选树的大小就是 \(minn-max+new\)，我们所求则是 \(min\{minn-max+new\}\)。

但是这样求得的是非严格次小，而不是严格。

当 \(new=max\) 时，若按上述方法进行维护，得到的 \((minn-max+new)=minn\)。

此时，就应该选择环上树边的次大值 \(nexm\)，\((minn-nexm+new)>minn\)。

现在的问题就在于，如何快速求出两点间树边的最大值和次大值。

若直接用两个二维数组直接将最大值，次大值存下来是不现实的，空间不允许。

用倍增的思想，可以存下来每个节点到其 \(2^k\) 级祖先的最大值和次大值。

比如，求从 u 到 v 的最大值，可以先找出 u 和 v 的 lca，然后分别求出 u 到 lca 和 v 到 lca 的最大值，两者取最大即可。

Code:

#include
#include
#include
#define int long long
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=3e5+7;
int n,m,minn,ans=1e18;
int fa[inf];
struct kruskal{
	int from,to,val;
	bool operator <(const kruskal &b)const
	{
		return valk;
struct edge{
	int to,val;
	edge(int to,int val):
		to(to),val(val){}
};
vectore[inf];
bool vis[inf<<1];int cnt;
int find(int s)
{
	if(s==fa[s])return s;
	return fa[s]=find(fa[s]);
}
int dep[inf],fat[inf][20];
int maxn[inf][20],nexm[inf][20];
void dfs(int now,int from)
{
	dep[now]=dep[from]+1;
	fat[now][0]=from;
	for(int i=0;ib?a:b;}
int _lca(int x,int y)
{
	if(dep[x]=0;i--)
		if(dep[fat[x][i]]>=dep[y])
			x=fat[x][i];
	if(x==y)return x;
	for(int i=19;i>=0;i--)
		if(fat[x][i]!=fat[y][i])
			x=fat[x][i],y=fat[y][i];
	return fat[x][0];
}
int ask(int x,int y,int z)
{
	int maxi=0;
	for(int i=19;i>=0;i--)
	{
		if(dep[fat[x][i]]>=dep[y])
		{
			if(maxn[x][i]==z)
				maxi=max(maxi,nexm[x][i]);
			else maxi=max(maxi,maxn[x][i]);
			x=fat[x][i];
		}
	}
	return maxi;
}
signed main()
{
	n=re();m=re();ans+=7;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		kruskal data;
		data.from=re(),data.to=re(),data.val=re();
		k.push_back(data);
	}
	sort(k.begin(),k.end());
	for(int i=0;imaxn[fat[j][i-1]][i-1])
				nexm[j][i]=max(nexm[j][i-1],maxn[fat[j][i-1]][i-1]);
		}
	}
	for(int i=0;i