代码：（时间复杂度：nlogn）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int maxn = 100005;
struct node {
int to,next;
} edges[maxn<<1];
//注意head[]数组初始化
int head[maxn],cnt,dp[maxn][15],dep[maxn];
void add(int u, int v) {
edges[cnt].to=v;
edges[cnt].next=head[u];
head[u]=cnt++;
}
//节点 父亲节点
void dfs(int s, int x) {
dp[s][0]=x;
dep[s]=dep[x]+1;
int t;
//跟新到根节点一路上的祖先
for(int i=1; (1<<i)<=dep[x]; ++i) dp[s][i]=dp[dp[s][i-1]][i-1];
for(int i=head[s]; i!=-1; i=edges[i].next) {
t=edges[i].to;
if(t==x) continue;
dfs(t,s);
}
}
int lca(int u, int v) {
if(dep[v]>dep[u]) swap(u,v);
for(int i=14; i>=0; --i) {
if((dep[u]-dep[v])>=(1<<i)) {
u=dp[u][i];
}
}
//此时深度一定相同
if(u==v) return u;
for(int i=14; i>=0; --i) {
if((1<<i)<=dep[u]&&dp[u][i]!=dp[v][i]) {
u=dp[u][i];
v=dp[v][i];
}
}
//循环过程中不加判断可能会超过最近公共祖先，所以跟新到lca的儿子节点即可
return dp[u][0];
}
int main() {
int n,m,u,v;
scanf("%d %d",&n,&m);
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1; i<n; ++i) {
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
dep[0]=1;
dfs(1,1);
for(int i=1; i<=m; ++i) {
scanf("%d %d",&u,&v);
printf("%d
",lca(u,v));
}
return 0;
}