自动搬运

查看原文

来自洛谷，原作者为

	yanzixuan2024 这个家伙很懒，可是 支持无条件壶关|忘关私信|骗关拉黑

搬运于2025-08-24 23:12:56，当前版本为作者最后更新于2025-08-18 20:26:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为每个点 $x$ 的操作都建立在它所属于的 $c_x$ 上，所以我们连边、建图都是 $c_i$ 来操作。题目要求我们为每条路线计算逃跑时在地面上跑动的最短距离，我们就可以建图，跑一遍最短路。

因为边权全部为 $1$，所以考虑 BFS。保存每一个点从起点到达的最短路径 $step$，但注意 $step$ 初始化全部为 $-1$。$step$ 初始化为 $0$ 时只有 $45$ 分，因为在自环情况下，初始化为 $0$ 就是把自己认作了自己的邻居，使得自己到自己的距离为 $1$。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n,m,c[maxn];
vector<int> vec[maxn];
int step[maxn];
int bfs(int st,int en){
	memset(step,-1,sizeof step);
	queue<int> q;
	q.push(st),step[st]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		if(u==en) return step[en];
		for(auto i:vec[u]){
			if(step[i]==-1) q.push(i),step[i]=step[u]+1;
		}
	}
	return 0;
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",c+i);
	for(int i=1;i<n;++i){
		int x,y;
		scanf("%d %d",&x,&y);
		vec[c[x]].push_back(c[y]),vec[c[y]].push_back(c[x]);
	}
	while(m--){
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",bfs(c[x],c[y]));
	}
}