题解：P12126 [蓝桥杯 2024 省 B 第二场] 狡兔 k 窟

· · 题解

因为每个点 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]));
    }
}