[题目链接：http://caioj.cn/problem.php?id=1236][40eebe4d]

代码：（时间复杂度：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\n",lca(u,v));

    }

    return 0;

}