自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 22:23:45，当前版本为作者最后更新于2020-08-18 16:42:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置思想：Kruskal 重构树

在讲解原题的算法前，先简单介绍一下 Kruskal 重构树的思想。一个经典问题：

给一张无向图 $G$，边有边权。每次询问给定 $x,v$，求从 $x$ 出发只经过边权 $\leq v$ 的边能到达多少个点。强制在线。

众所周知，图上两点的最小瓶颈路（也就是最大边最小的路）一定包括最小生成树上两点的路。所以我们可以先把边排序，用 Kruskal 算法求出最小生成树。但这样仍然不能方便地求出答案，怎么办呢？Kruskal 重构树的思想是：在 Kruskal 算法确定一条最小生成树上的边 $(x,y)$ 时，不直接连接 $(x,y)$，而是新建一个节点 $T$，分别连接 $(T,x),(T,y)$，将 $T$ 的点权设置为 $x,y$ 的边权，这就形成了 Kruskal 重构树。容易发现一些性质：

• 对于每个点 $x$，$x$ 祖先上的点权单调递增。
• 对于每个点 $x$ 和每个阈值 $v$，从 $x$ 出发只经过边权 $\leq v$ 的边能到达的点的集合，和 $x$ 祖先节点中深度最大的 $\leq v$ 的节点的子树内的所有原图节点的集合是一样的。这样就可以解决上面的题目了。
• 对于两点 $x,y$，$x,y$ 的最小瓶颈边权（也就是最大边最小的路的最大边权）等于 $x,y$ 的最近公共祖先（LCA）的点权。

关于更详细的讲解，请见 NOI2018 归程 一题的题解。

对于本题来说，也可以理解为是查询两点间的瓶颈边，我们尝试运用类似 Kruskal 重构树的思想。

首先分析原题中的描述，可以知道：两点 $x,y$ 能互相派出使者访问，当且仅当两点连通，且它们所在的连通块不是一条链。 证明较为简单，连通性显然必须满足，而如果连通块是链也显然无解，尝试一下发现只要有度数 $\geq 3$ 的点或者环那么必定有解。

将边从小到大排序，运行和 Kruskal 算法类似的过程。不同的是，我们不仅要维护连通性，还要维护一个连通块究竟是不是链。发现一条链的性质很大程度上取决于两个端点，于是不妨在并查集的根节点处维护两个数组 $st_i,en_i$，如果该连通块是链，则存储链的端点。当一个连通块从链变成非链时，我们就在 Kruskal 重构树上新建一个节点，这个节点向所有链上的点连边；连通块合并同理。不难发现这样做仍然能保证原来 Kruskal 重构树的大部分性质，而且也能用 LCA 来处理在线询问。

简单来说，我们扫描每条边：

1. 如果边两端已经连通：如果这个连通块是一条链，那么加上这条边显然不再是链了，那么打上标记，同时在 Kruskal 重构树上连边；否则没有变化。
2. 如果没有连通：

• 如果原来两个连通块有至少一个不是链，那么新连通块也一定不是链；
• 如果原来两个连通块都是链，那么新连通块是不是链取决于连边是不是在端点之间进行的。也可简单维护。

注意我们由于要维护一个点所在的连通块，且要支持合并，应采用启发式合并，使时间复杂度稳定在 $O(n\log n)$。

总时间复杂度 $O((n+q)\log n)$。

下面是代码，其中并查集 $B$ 用来维护连通性，$conn_i$ 表示并查集里以 $i$ 为根的连通块是不是脱离链的形态了，$tr$ 表示 Kruskal 重构树的边。

#include"swap.h"

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct BCJ
{
	int fa[500000];
	void init(int n){for(int i=0;i<n;i++)fa[i]=i;}
	int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
}B;

struct e
{
	int u,v,w;e(int uu=0,int vv=0,int ww=0):u(uu),v(vv),w(ww){}
};vector<e> ed;
bool operator<(e a,e b){return a.w<b.w;}

bool conn[500000];int st[500000],en[500000],rt[500000];vector<int> pnt[500000];

vector<int> tr[500000];

int fa[500000][20],dep[500000];

void dfs(int u,int f)
{
	fa[u][0]=f;for(int i=1;i<20;i++)fa[u][i]=fa[u][i-1]==-1?-1:fa[fa[u][i-1]][i-1];
	rt[u]=f==-1?u:rt[f],dep[u]=f==-1?1:dep[f]+1;
	for(int i=0;i<tr[u].size();i++)dfs(tr[u][i],u);
}

int LCA(int x,int y)
{
	if(rt[x]!=rt[y])return -1;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--)
	{
		if(fa[x][i]!=-1&&dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(int i=19;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
int n,m;
void init(int N, int M,vector<int> U,vector<int> V,vector<int> W)
{
	n=N,m=M;
	for(int i=0;i<M;i++)ed.push_back(e(U[i],V[i],W[i]));sort(ed.begin(),ed.end());
	B.init(N);for(int i=0;i<N;i++)st[i]=en[i]=rt[i]=i,pnt[i].push_back(i);
	for(int i=0;i<M;i++)
	{
		int u=ed[i].u,v=ed[i].v,fu=B.fnd(u),fv=B.fnd(v);
		if(pnt[fu].size()<pnt[fv].size()){swap(u,v),swap(fu,fv);}
		if(fu==fv)
		{
			if(!conn[fu])
			{
				conn[fu]=1;
				for(int j=0;j<pnt[fu].size();j++)tr[i+N].push_back(pnt[fu][j]);
				rt[fu]=i+N;
			}
		}
		else
		{
			if(conn[fu]||conn[fv])
			{
				if(conn[fu])tr[i+N].push_back(rt[fu]);
				else for(int j=0;j<pnt[fu].size();j++)tr[i+N].push_back(pnt[fu][j]);
				if(conn[fv])tr[i+N].push_back(rt[fv]);
				else for(int j=0;j<pnt[fv].size();j++)tr[i+N].push_back(pnt[fv][j]);
				conn[fu]=1,rt[fu]=i+N;B.fa[fv]=fu;
			}
			else
			{
				if((u==st[fu]||u==en[fu])&&(v==st[fv]||v==en[fv]))
				{
					st[fu]=u^st[fu]^en[fu];en[fu]=v^st[fv]^en[fv];
					for(int j=0;j<pnt[fv].size();j++)pnt[fu].push_back(pnt[fv][j]);
					B.fa[fv]=fu;
				}
				else
				{
					conn[fu]=1;
					for(int j=0;j<pnt[fu].size();j++)tr[i+N].push_back(pnt[fu][j]);
					for(int j=0;j<pnt[fv].size();j++)tr[i+N].push_back(pnt[fv][j]);
					B.fa[fv]=fu;rt[fu]=i+N;
				}
			}
			
		}
	}
	/*for(int i=0;i<N+M;i++)
	{
		printf("%d: ",i);
		for(int j=0;j<tr[i].size();j++)printf("%d ",tr[i][j]);puts("");
	}*/
	for(int i=N+M-1;i>=0;i--)
	{
		if(!dep[i])dfs(i,-1);
	}
	//for(int i=0;i<N+M;i++){printf("%d\n",dep[i]);for(int j=0;j<4;j++)printf("%d ",fa[i][j]);puts("");}
}

int getMinimumFuelCapacity(int X,int Y)
{
	
	int u=LCA(X,Y);if(u==-1)return -1;
	return ed[u-n].w;
}