D11 树链剖分 P3379【模板】最近公共祖先（LCA）
重链求LCA：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N]; 
int fa[N],dep[N],siz[N],son[N],top[N];
//第一个 DFS 记录每个结点的父节点（fa）、深度（dep）、子树大小（siz）、重子节点（son）。
void dfs1(int x,int xfa)
{
    fa[x]=xfa;dep[x]=dep[xfa]+1;siz[x]=1;son[x]=-1;
    for(int y:G[x])if(y!=xfa)
    {
        dfs1(y,x);
        siz[x]+=siz[y];
        if(son[x]==-1 || siz[son[x]]<siz[y])son[x]=y;
    }
}
//第二个 DFS 记录每个节点所在链的链顶（top）。
void dfs2(int x,int tp)
{
    top[x]=tp;
    if(son[x]>0)dfs2(son[x],tp);
    for(int y:G[x])if(y!=fa[x] && y!=son[x])
        dfs2(y,y);
}

int LCA(int x,int y)
{
    for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x, y);
	return dep[x]<dep[y] ? x : y;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}