根为r时x、y的公共祖先，就是lca(x,r),lca(x,y),lca(r,y)中深度最大的那一个，不要再在倍增的时候判来判去还判不对了...
1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6 const int maxn=3e5+10; 7 8 inline ll rd(){ 9 ll x=0;char c=getchar();int neg=1; 10 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*neg; 13 } 14 15 int eg[maxn*2][2],egh[maxn],ect; 16 int dfn[maxn][2],tot; 17 int dep[maxn],fa[maxn][20]; 18 int N,M; 19 20 inline void adeg(int a,int b){ 21 eg[++ect][0]=b;eg[ect][1]=egh[a];egh[a]=ect; 22 } 23 24 void dfs(int x){ 25 for(int i=0;fa[x][i]&&fa[fa[x][i]][i];i++){ 26 fa[x][i+1]=fa[fa[x][i]][i]; 27 } 28 for(int i=egh[x];i;i=eg[i][1]){ 29 int b=eg[i][0];if(b==fa[x][0]) continue; 30 dep[b]=dep[x]+1,fa[b][0]=x; 31 dfs(b); 32 } 33 } 34 35 int lca(int x,int y){ 36 if(dep[x]<dep[y]) swap(x,y); 37 for(int i=log2(dep[x]-dep[y]+1);i>=0;i--){ 38 if(fa[x][i]&&dep[fa[x][i]]>=dep[y]) 39 x=fa[x][i]; 40 } 41 if(x==y) return x; 42 for(int i=log2(dep[x]);i>=0;i--){ 43 if(fa[x][i]&&fa[y][i]&&fa[x][i]!=fa[y][i]) 44 x=fa[x][i],y=fa[y][i]; 45 } 46 return fa[x][0]; 47 } 48 49 int main(){ 50 //freopen("","r",stdin); 51 int i; 52 N=rd(),M=rd(); 53 for(i=1;i<N;i++){ 54 int a=rd(),b=rd(); 55 adeg(a,b);adeg(b,a); 56 } 57 dep[1]=1;dfs(1); 58 for(i=1;i<=M;i++){ 59 int r=rd(),x=rd(),y=rd(); 60 int a=lca(x,y),b=lca(x,r),c=lca(y,r); 61 int mm=max(dep[a],max(dep[b],dep[c])); 62 if(dep[a]==mm) printf("%d ",a); 63 else if(dep[b]==mm) printf("%d ",b); 64 else printf("%d ",c); 65 } 66 return 0; 67 }