求助基于 Tarjan 的 LCA

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+4;
#define int short 
#define pii pair<int,int>
int n,r,m;
int u,v;
vector<int>G[N];
vector<pii>Q[N];
int fa[N],ans[N];
bool vis[N];
int cnt;
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs(int u){
	fa[u]=u;
	vis[u]=1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(vis[v]){
			continue;
		}
		dfs(v);
		fa[v]=u;
	}
	for(int i=0;i<Q[u].size();i++){
		int v=Q[u][i].first;
		if(vis[v]){
			ans[Q[u][i].second]=find(v);
		}
	}
} 
int ds[N];
int x;
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>r>>m;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cnt++;
			Q[i].push_back({j,cnt});
			Q[j].push_back({i,cnt});
		}
	}
	dfs(r);
	for(int i=1;i<=cnt;i++){
		ds[ans[i]]++;
	}
	while(m--){
		cin>>x;
		cout<<ds[x]<<"\n";
	}
return 0;
}