错误只有一处,就是fa应该在tarjan里初始化,具体原因,我也不清楚qwq
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,m,s;
int fa[N];
vector<int>e[N];
vector<pair<int,int>>query[N];
int vis[N],ans[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void tarjan(int u){
fa[u]=u,vis[u]=1;//
for(auto v:e[u]){
if(!vis[v]){
tarjan(v);
fa[v]=u;
}
}
for(auto q:query[u]){
int v=q.first,i=q.second;
if(vis[v]){
ans[i]=find(v);
}
}
}
int main(){
cin>>n>>m>>s;
//for(int i=0;i<=N;i++) fa[i]=i;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
query[a].push_back({b,i});
query[b].push_back({a,i});
}
tarjan(s);
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
return 0;
}
```
by cat_lover1 @ 2024-04-04 15:06:50
fa可以不用在tarjan函数里初始化,错误原因在于fa初始化下标越界,只能到N-1
by wt1551 @ 2024-04-11 08:57:59