LCA-树剖

树剖，全称树链剖分，其中已重链剖分较为常用（还有实链剖分，但是与此题无关）

此题主要用到树剖的两个dfs所得的top,dfn(dep),size,fa,son数组。接着讲讲各个数组的含义。

第一次dfs： dfn(dep): 该点深度 size: 已该点为根的子树包含的节点个数 fa: 略 son: 该点子节点中size最大的(即最重的子节点)

第二次dfs： top: 该点所在的链的顶端(深度最小的点)

然后每次将深度大的点往上跳一条链，直到两个点在同一链上。

#include <algorithm> //STL通用算法
#include <cmath> //定义数学函数
#include <cstdio> //定义输入/输出函数
#include <iostream> //数据流输入/输出
#include <cstring> //字符串处理
#include <string> //字符串类
#include <ctime> //定义关于时间的函数
#define itn int
#define fro for
/*#include <bitset> //STL位集容器
#include <cstype> //字符处理
#include <cerrno> //定义错误码
#include <complex> //复数类
#include <clocale> //定义本地化函数
#include <cstdlib> //定义杂项函数及内存分配函数
#include <deque> //STL双端队列容器
#include <exception> //异常处理类
#include <fstream> //文件输入/输出
#include <functional> //STL定义运算函数(代替运算符)
#include <limits> //定义各种数据类型最值常量
#include <list> //STL线性列表容器
#include <map> //STL映射容器
#include <iomanip> //参数化输入/输出
#include <ios> //基本输入/输出支持
#include <iosfwd> //输入/输出系统使用的前置声明
#include <istream> //基本输入流
#include <ostream> //基本输出流
#include <queue> //STL队列容器
#include <set> //STL集合容器
#include <sstream> //基于字符串的流
#include <stack> //STL堆栈容器
#include <stdexcept> //标准异常类
#include <streambuf> //底层输入/输出支持
#include <utility> //STL通用模板类
#include <vector> //STL动态数组容器
#include <cwchar.h>//宽字符处理及输入/输出
#include <cwctype.h> //宽字符分类*/

using namespace std;

int ans;

int max(int x,int y){
    return x>y?x:y;
}

int min(int x,int y){
    return x<y?x:y;
}

int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}

void write(int x){
    int buf[50];
    if (x<0) putchar('-'),x=-x;
    buf[0]=0;
    while (x) buf[++buf[0]]=x%10,x/=10;
    if (!buf[0]) buf[0]=1,buf[1]=0;
    while (buf[0]) putchar('0'+buf[buf[0]--]);
}

struct p{
    int to,v,next;
}e[10001000];

int cnt;int last[10001000],dfn[10001000],son[10001000],top[10001000],size[10001000],fa[10001000];

void add(int a,int b,int v){
    e[++cnt]=(p){b,v,last[a]},last[a]=cnt;
} 

void dfs1(int x){
    dfn[x]=dfn[fa[x]]+1;size[x]=1;
    for(int i=last[x];i;i=e[i].next){
        int to=e[i].to;
        if(fa[x]!=to&&!fa[to]){
            fa[to]=x;
            dfs1(to);
            size[x]+=size[to];
            if(size[son[x]]<size[to]) son[x]=to;
        }
    }
}

void dfs2(int x){
    if(x==son[fa[x]])top[x]=top[fa[x]];
    else top[x]=x;
    for(int i=last[x];i;i=e[i].next)if(fa[e[i].to]==x) dfs2(e[i].to);
}

int main(){
    int q,w;
    int n=read(),m=read(),s=read();
    for (int i=1;i<=n-1;i++){
        q=read();w=read();
        add(q,w,0);add(w,q,0);
    }
    dfs1(s);
    dfs2(s);
    for (int i=1;i<=m;i++){
        int a=read(),b=read();
        while (top[a]!=top[b]){
            if (dfn[top[a]]>dfn[top[b]]) a=fa[top[a]];
            else b=fa[top[b]];
        }
        write(dfn[a]<dfn[b]?a:b);
        if (i!=m) putchar('\n');
    }
    return 0;
}