不知道哪里错了,感觉自己思路都是对的
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int num;
int cos;
}f[203030][40];
vector<int>P[102020];
int cnt;
int cnt2;
int dfn[102020];
int memor[102020];
int dep[102020];
int dfs(int u,int deep)
{
if(!dfn[u])
{
dfn[u]=++cnt;
dep[u]=deep;
memor[u]=++cnt2;
f[cnt2][0].cos=dep[u];
f[cnt2][0].num=u;//f[0]储存初始欧拉序
}
for(int i=0;i<P[u].size();i++)
{
int k=P[u][i];
if(!dfn[k])
{
dfs(k,deep+1);
f[++cnt2][0].cos=deep;
f[++cnt2][0].num=u;
}
}
return 0;
}
int N,M,S;
int logn[102020];
int main()
{
cin>>N>>M>>S;
for(int i=1;i<N;i++)
{
int x,y;
cin>>x>>y;
P[x].push_back(y);
P[y].push_back(x);
}
logn[0]=-1;
for(int i=1;i<=N;i++)
{
logn[i]=logn[i>>1]+1;
}
dfs(S,1);
for(int j=1;j<=logn[N];j++)
{
for(int i=1;(i+(1<<j)-1)<=N;i++)
{
if(f[i][j-1].cos<f[i+(1<<(j-1))][j-1].cos)
{
f[i][j]=f[i][j-1];
}
else f[i][j]=f[i+(1<<(j-1))][j-1];
}
}//ST表处理
for(int i=1;i<=M;i++)
{
int l,r;
cin>>l>>r;
l=memor[l];
r=memor[r];//找到第一次出现的位置
int x=logn[r-l+1];
if(f[l][x].cos<f[r-(1<<x)+1][x].cos)
cout<<f[l][x].num<<endl;
else cout<<f[r-(1<<x)+1][x].num<<endl;
}
return 0;
}