#include 
     
      #define read read()#define up(i,l,r) for(register int i = (l);i <= (r);i++)#define down(i,l,r) for(register int i = (l);i >= (r);i--)#define traversal_vedge(i) for(register int i = head[u]; i ;i = e[i].nxt)#define ll long longusing namespace std;int read{    int x = 0, f = 1; char ch = getchar();    while(ch < 48 || ch > 57) {
   if(ch == '-')f = -1; ch = getchar();}    while(ch >=48 && ch <=57) {x = 10 * x + ch - 48;ch = getchar();}    return x * f; }int n,m,s;const int N = 500005;int dep[N],fa[N],size[N],top[N];struct edge{    int v,nxt;}e[N<<1];int cnt,head[N];void add(int u,int v){    e[++cnt] = (edge){v,head[u]};    head[u] = cnt;}void readdata(){    n = read; m = read; s = read;    up(i,1,n-1)    {        int u = read,v = read;        add(u,v);        add(v,u);    }}//-----------------------------------------------------------------------void dfs(int u){    dep[u] = dep[fa[u]] + 1;    size[u] = 1;    top[u] = u;    //debug 未写 top[u] = u;     int heavyson_id = 0,heavyson_size = 0;    traversal_vedge(i)    {        int v = e[i].v;        if(v == fa[u]) continue;        fa[v] = u; //top[v] = u;                 //debug 不写top[v] = u;        dfs(v);        size[u] += size[v];        //heavyson = max(heavyson,size[v]);        if(size[v] > heavyson_size) heavyson_id = v,heavyson_size = size[v];     }    if(heavyson_id) top[heavyson_id] = u;//debug heavyson_id -> u;    //有重儿子才更新top[]     //dfs后,top[]只相当于重链上的fa[]         //调用find(u)过后,从u到链首的所有top[]才指向链首; }int find(int u){    if(u == top[u]) return u;    top[u] = find(top[u]);//debug top[u] -> u    return top[u];    //逆向搜索,并修改值; }int lca(int x,int y){    if(find(x) != find(y)) //如果不在一条链上    //**一条链:重链为一条链,轻链单独一条边为一条链;    {        if(dep[top[x]] > dep[top[y]]) return lca(fa[top[x]] , y);//debug fa[top[x]] -> fa[dep[top[x]]];        else return lca(x , fa[top[y]]);    }    return dep[x] > dep[y] ? y : x;}void work(){    dfs(s);    while(m--)    {        int a = read,b = read;        printf("%d\n",lca(a,b));     }}int main(){    freopen("input.txt","r",stdin);    readdata();    work();    return 0;}
     

总结:

树链剖分版的LCA的dfs1稍有不同，不需要用数组记录每个点的重儿子；

树链剖分维护7个数组，树链剖分——LCA维护4个数组（fa[],dep[],size[],top[]）son[]简化成heavyson_id