自动搬运

查看原文

来自洛谷，原作者为

	Eternatis 幾重にも辛酸を舐め、七難八苦を越え、艱難辛苦の果、満願成就に至る。

搬运于2025-08-24 23:10:22，当前版本为作者最后更新于2025-02-23 19:47:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我永远喜欢 Neri 酱！

先考虑最优策略是什么：假设我们从点 $s$ 出发，首先如果有一个与 $s$ 相邻的 $p$ 满足 $p<s$，则我们显然不增加答案就可以直接访问 $p$。不妨维护一个当前可以任意访问的连通块，则上面的操作就是直接把编号不超过 $s$ 的相邻点并入连通块。

在所有这样的操作都做完后，与连通块相邻的所有点编号都大于 $s$。这时如果 $t$ 已经在连通块中，则答案就是 $1$；否则我们令答案加一，并访问当前能访问的编号最大的点，这是因为我们的路径可以经过重复的点和边，访问完编号最大的点后原路返回一定也能访问其他的点。

这个过程看起来很能倍增，考虑求出以每个点为起点，其对应的连通块能到达的权值最大的点。我们按照编号从小到大的顺序求解，对当前点 $x$，遍历 $x$ 的所有邻接点 $y$，如果 $y<x$，就与 $y$ 所在连通块的答案取 $\max$，否则就与 $y$ 取 $\max$。最后再合并 $x$ 与小于 $x$ 的 $y$ 对应的连通块。

现在对于一个询问，我们就可以倍增得到 $u$ 走若干步能到达的点编号的范围了，唯一的问题是：我们如何判断倍增后是否能到达 $v$？考虑求出所有 $u$ 到 $v$ 的路径中，最大点权的最小值，如果当前能访问的点权不小于这个值，则 $v$ 已经在当前连通块中。我们令一条 $(u,v)$ 边的权值为 $\max(u,v)$，则上面的问题等价于最小瓶颈路，建出 Kruskal 重构树后求 LCA 即可。

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

code :

#include<bits/stdc++.h>
using namespace std;
#define N    1000010
#define int  long long
#define pb   push_back
#define il   inline
il int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int T=1,n,m,q,k;
int s[N];
char c[N];
vector<int> v[N];
int w[N],ww[N];
int to[21][N];
struct node{
	int x,y,z;
}e[N];
il bool cmp(const node &a,const node &b){
	return a.z<b.z;
}
int tot,f[N];
il int fd(int x){
	if(x==f[x])return x;
	return f[x]=fd(f[x]);
}
int val[N];
vector<int> V[N];
il void link(int x,int y,int z){
	int a=fd(x),b=fd(y);
	if(a==b)return ;
	val[++tot]=z;
	f[a]=f[b]=tot;
	V[tot].pb(a),V[tot].pb(b);
}
int fa[21][N],dep[N];
il void dfs(int x){
	for(int i=1;i<=20;i++)
		fa[i][x]=fa[i-1][fa[i-1][x]];
	for(auto y:V[x]){
		fa[0][y]=x;
		dep[y]=dep[x]+1;
		dfs(y);
	}
}
il int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[fa[i][x]]>=dep[y])
			x=fa[i][x];
	if(x==y)return x;
	for(int i=20;i>=0;i--)
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}
il void solve(){
	tot=n=read();m=read();q=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		e[i].x=x,e[i].y=y,e[i].z=max(x,y);
		v[x].pb(y),v[y].pb(x);
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n*2;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		link(e[i].x,e[i].y,e[i].z);
	}
	dfs(tot);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=n;i++)w[i]=i;
	for(int x=1;x<=n;x++){
		for(auto y:v[x]){
			if(y<x)w[x]=max(w[x],ww[fd(y)]);
			else w[x]=max(w[x],y);
		}
		ww[x]=w[x];
		for(auto y:v[x]){
			if(y<x){
				int a=fd(x),b=fd(y);
				if(a==b)continue;
				ww[b]=max(ww[b],ww[a]);
				f[a]=b;
			}
		}
	}
	for(int i=1;i<=n;i++)to[0][i]=w[i];
	for(int k=1;k<=20;k++)for(int i=1;i<=n;i++)to[k][i]=to[k-1][to[k-1][i]];
	while(q--){
		int x=read(),y=read();
		int aaa=val[lca(x,y)];
		if(x>=aaa){
			puts("1");
			continue;
		}
		int sum=0;
		for(int k=20;k>=0;k--)
			if(to[k][x]<aaa){
				sum+=(1<<k);
				x=to[k][x];
			}
		printf("%lld\n",sum+2);
	}
}
signed main(){
	T=1;
	while(T--)solve();
	return 0;
}