原理细节参考链接： https://www.cnblogs.com/dx123/p/16320461.html
例题：
景区导游（树上前缀和+LCA）https://www.acwing.com/activity/content/code/content/8479608/
零食采购 https://www.acwing.com/blog/content/54782/
砍树（树上差分+LCA） https://www.acwing.com/activity/content/code/content/8486157/

模板易错点
1.dfs时不能忘记if(t!=father) dfs(t,u);否则无限遍历
2.for(int i=19;i>=0;i–) 中注意i>=0,不是i，i可以为0

模板

#include <iostream>
#include <vector> 
using namespace std;
const int N=5e5+10;
vector<int>e[N];
int dep[N];  //dep[u]代表u节点的深度
int fa[N][20];  //2^19次方大于等于5e5，fa[u][i]存储u节点向上跳2^i层到达的父节点

//dfs打表，将dep和fa数组初始化 
void dfs(int u,int father)
{
    //dep数组赋值 
    dep[u]=dep[father]+1;

    //先将直接父节点赋值，供之后fa数组从左往右递推 
    fa[u][0]=father;
    for(int i=1;i<=19;i++)  
        fa[u][i]=fa[fa[u][i-1]][i-1]; //分两次跳，先跳2^(i-1)层到fa[u][i-1]节点,再跳2^(i-1)层

    //计算子节点 
    for(auto t:e[u])
        if(t!=father)   dfs(t,u);
}

//求最短公共祖先 
int lca(int u,int v)
{
    //确定较低层 
    if(dep[u]<dep[v])   swap(u,v);

    //先将u和v跳到同一层 
    for(int i=19;i>=0;i--)  //从高到低跳才能凑出任何u和v之间差的高度，类似于一个十进制数用二进制位凑，从大往小凑
    {
        //保证u跳的位置的高度  低于或等于  v的高度
        if(dep[fa[u][i]]>=dep[v])   u=fa[u][i];
    }

    //如果v本身就是u的祖先
    if(u==v)    return v;

    //u，v一起跳到公共祖先
    for(int i=19;i>=0;i--)
    {
        //保证u和v跳到的位置不是同一个位置，这样最后才会把u和v限制到最短公共祖先的直接子节点
        if(fa[u][i]!=fa[v][i])  u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0]; 
}

int main()
{
    int n,m,s;cin>>n>>m>>s;
    for(int i=0;i<n-1;i++)
    {
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    dfs(s,0);

    while(m--)
    {
        int a,b;cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    return 0;
}