之前写的过了加了数据之后就T飞了。。
复杂度是对的啊
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
int to,next;
}a[1000000];
int h[500000],d[500000],prt[500000],p[500000][25],n,m,root,cnt;
void addedge(int x,int y){
a[++cnt].to=y;
a[cnt].next=h[x];
h[x]=cnt;
}
void dfs(int x,int fa,int depth){
d[x]=depth;
for(int i=h[x];i;i=a[i].next){
if(a[i].to!=fa)dfs(a[i].to,x,depth+1);
prt[a[i].to]=x;
}
}
void st(){
memset(p,-1,sizeof(p));
for(int i=1;i<=n;i++)p[i][0]=prt[i];
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j<=n;j++){
if(p[j][i-1]!=-1)p[j][i]=p[p[j][i-1]][i-1];
}
}
}
int lca(int a,int b){
if(d[a]<d[b])swap(a,b);
int k=log2(d[a]);
for(int i=k;i>=0;i--){
if(d[a]-pow(2,i)>=d[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k;i>=0;i--){
if(p[a][i]!=-1&&p[a][i]!=p[b][i]){
a=p[a][i];
b=p[b][i];
}
}
return p[a][0];
}
void read(){
int x,y;
cin>>n>>m>>root;
for(int i=1;i<=n-1;i++){
cin>>x>>y;
addedge(y,x);
addedge(x,y);
}
}
void getans(){
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
}
signed main(){
memset(p,0,sizeof(p));
read();
dfs(root,0,1);
st();
getans();
return 0;
}