kruskal 重构树

用途

巧妙地求解询问连接两点的所有路径中最大边的最小值或者最小边的最大值问题。

思路

kruskal 求 MST 的时候是逐步加边，而 kruskal 重构树则是将要加的边转化成点，并连接原来的两个点，边权为点权。

就像这样：

实例（图片来自 OI-Wiki）

原无向图

重构树

性质

• kruskal 重构树是一棵二叉堆
• 最小生成树的重构树是大根堆，最大生成树的重构树是小根堆
• 图上两点最小路径的最大值或最大路径的最小值为重构树上两点的 lca 的点权。
• 重构树上共 \(n\times 2-1\) 的点，其中，n 个叶节点为原来图中的节点。

例题讲解

归程

这个题可以用可持久化并查集切掉。

原谅我不会

海拔比水位高的路车可以通过，剩下的路只能步行涉水。

那么就先预处理出整张图的 kruskal 重构树，然后找到树上的一个节点 x，满足 val[x]>p&&val[fa[x]]<=p，这样，以 x 为根的子树中的叶节点就是能通过车连通的。

提前预处理出图上每个节点到 1 号节点的最短路，然后在重构树中维护每个节点为根时子树中距离 1 号节点的最小值。

至于怎么找到重构树上的节点 x，那就要用到倍增了。

坑点

1. 最短路用 dijkstra，因为 SPFA 死了。
2. 多测记得清空，尤其是 lastans 容易忘。

Code

#include
#include
#include
#include
#include
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=4e5+7;
int t,n,m,q,k,s,last;
int fir[inf],nex[inf<<1],poi[inf<<1],val[inf<<1],cnt;
void ins(int x,int y,int z)
{
	nex[++cnt]=fir[x];
	poi[cnt]=y;
	val[cnt]=z;
	fir[x]=cnt;
}
int dis[inf];bool vis[inf];
struct dij{
	int id,dis;
	dij(int id,int dis):id(id),dis(dis){}
	bool operator <(const dij &b)const
	{
		return dis>b.dis;
	}
};
struct kruskal{
	int from,to,val;
	bool operator <(const kruskal &b)const
	{
		return val>b.val;
	}
};
int fat[inf],cntm,cntn;
int find(int x)
{
	if(x==fat[x])return fat[x];
	return fat[x]=find(fat[x]);
}
struct SR_heap{
	int lc,rc,val,minn;
	#define lc(i) T[i].lc
	#define rc(i) T[i].rc
};
SR_heap T[inf];
int fa[inf][20];
void dfs(int now,int from)
{
	fa[now][0]=from;
	if(lc(now)==0)
	{
		T[now].minn=dis[now];
		return;
	}
	dfs(lc(now),now);
	dfs(rc(now),now);
	T[now].minn=min(T[lc(now)].minn,T[rc(now)].minn);
}
int tiao(int x,int k)
{
	for(int i=19;i>=0;i--)
	{
		if(T[fa[x][i]].val<=k)continue;
		x=fa[x][i];
	}
	return x;
}
int main()
{
	t=re();
	while(t--)
	{
		cntn=n=re(),m=re();
		cnt=cntm=last=0;
		memset(fir,0,sizeof(fir));
		memset(nex,0,sizeof(nex));
		memset(poi,0,sizeof(poi));
		memset(val,0,sizeof(val));
		memset(dis,127,sizeof(dis));
		memset(vis,0,sizeof(vis));
		memset(fa,0,sizeof(fa));
		memset(T,0,sizeof(T));
		priority_queueheap;
		vectorh;
		for(int i=1;i<=m;i++)
		{
			int u=re(),v=re(),l=re(),a=re();
			ins(u,v,l),ins(v,u,l);
			h.push_back((kruskal){u,v,a});
		}
		heap.push(dij(1,0));dis[1]=0;
		while(heap.size())
		{
			dij now=heap.top();heap.pop();
			if(vis[now.id])continue;
			vis[now.id]=1;
			for(int i=fir[now.id];i;i=nex[i])
			{
				int p=poi[i];
				if(dis[p]>dis[now.id]+val[i])
				{
					dis[p]=dis[now.id]+val[i];
					heap.push(dij(p,dis[p]));
				}
			}
		}
		for(int i=1;i<=n;i++)fat[i]=i;
		sort(h.begin(),h.end());
		int len=h.size();
		for(int i=0;i