P12126 TLE 75pts求条

#include<bits/stdc++.h>
using namespace std;
const int MX=5e3+10;
int n,m;
int st[MX];
vector<int> v[MX];
bool vis[MX][MX];
bool lst[MX];
int rem[MX][MX];
int bfs(int x,int y){
	if(x==y)return 0;
	if(rem[x][y])return rem[x][y];
	int ans=0;
	memset(lst,0,sizeof(lst));
	queue<pair<int,int>> q;
	q.push({x,0});
	while(!q.empty()){
		pair<int,int> p=q.front();
		q.pop();
		for(int i=0;i<v[p.first].size();i++){
			if(lst[v[p.first][i]])continue;
			q.push({v[p.first][i],p.second+1});
			if(v[p.first][i]==y){
				ans=p.second+1;
				rem[x][y]=rem[y][x]=ans;
				return ans;
			}
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> st[i];
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin >> x >> y;
		x=st[x],y=st[y];
		if(!vis[x][y] && !vis[y][x]){
			vis[x][y]=vis[y][x]=1;
			v[x].push_back(y);
			v[y].push_back(x);
		}
	}
	while(m--){
		int p,q;
		cin >> p >> q;
		p=st[p],q=st[q];
		cout << bfs(p,q) << "\n";
	}
	return 0;
}