头铁撞墙-狡兔 k 窟

解题思路:

惯性思维硬刚等同于头铁撞墙

把连通的点集视为一个结点，结点相连，然后广搜路径
注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define MAX 0x3f3f3f3f

const int N = 5001;

typedef pair<int,int> pll;

map<pll,int> mp; vector<int> q[N]; queue<pll> p;

int main(){

         int n,m,i,j,a[N],x,y,v[N];

         cin>>n>>m;

         for(i=1;i<=n;i++) cin>>a[i];

         for(i=1;i<n;i++){

             cin>>x>>y; 

            if(a[x]>a[y]) swap(x,y);

             if(mp[pll(a[x],a[y])]) continue;

             mp[pll(a[x],a[y])]=1;

             q[a[x]].push_back(a[y]);

             q[a[y]].push_back(a[x]);

         }

        while(m--){

             cin>>x>>y; 

             if(a[x]==a[y]){ cout<<0<<'\n'; continue;}

             memset(v,0,sizeof(v));

             p.push(pll(a[x],0)); v[a[x]]=1; int f=0;

             while(!p.empty()){

                 pll k=p.front(); p.pop(); 

                 for(auto j: q[k.first]){

                     if(!v[j]){

                          if(a[y]==j){ f=1; cout<<k.second+1<<'\n'; break;}

                         p.push(pll(j,k.second+1)); 

                         v[j]=1;

                      }

               }

              if(f) while(!p.empty()) p.pop();

         }

    }

    return 0;

}