如题,想了很久还是找不到错,求各位大佬相助,感谢!
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll n,m,s;
vector<ll> v[600001];
ll f[600001][22];
ll depth[600001];
void dfs(ll x,ll fa){
f[x][0]=fa;depth[x]=depth[fa]+1;
for(ll i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
for(ll i=0;i<v[x].size();i++){
ll tmp=v[x][i];
if(tmp==fa)continue;
dfs(tmp,x);
}
}
ll LCA(ll x,ll y){
if(depth[x]>depth[y])swap(x,y);
for(ll i=20;i>=0;i--)if(depth[f[x][i]]>=depth[y])x=f[x][i];
if(x==y)return x;
for(ll i=20;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
return f[x][0];
}
int main(){
cin>>n>>m>>s;
for(ll i=1;i<n;i++){ll a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}
dfs(s,0);
while(m--){
ll x,y;cin>>x>>y;
cout<<LCA(x,y)<<endl;
}
return 0;
}