LCA

https://www.luogu.org/problemnew/show/P3379

知识点：1.倍增，2 << i

#include <bits/stdc++.h>
#define M 500002
using namespace std;
int n,m,rt;
struct edge
{
    int to;
    int nxt;
}e[M << 2];
int head[M << 1],cnt;
int dep[M],fa[M],f[M][30];
void add(int x,int y)
{
    e[++cnt].nxt = head[x];
    e[cnt].to = y;
    head[x] = cnt;    
} 
void dfs(int t,int fat,int deep)
{
    dep[t] = deep;
    fa[t] = fat;
    f[t][0] = fat;
    for(int i = head[t];i;i = e[i].nxt)
    {
        int y = e[i].to;
        if(y != fat)
        {
            dfs(y,t,deep + 1);
        }
    }
}
void get(int t)
{
    for(int i = 1;1 << i < dep[t];i++)//这里应为1 << i,不是2 << i 
    {
        f[t][i] = f[f[t][i - 1]][i - 1];
    }
    for(int i = head[t];i;i = e[i].nxt)
    {
        int y = e[i].to;
        if(y != fa[t])
        {
            get(y);
        }
    }
}
int lca(int x,int y)
{
    if(dep[x] > dep[y])swap(x,y);
        for(int i = 20;i >= 0;i--)
        {
            if(1 << i <= dep[y] - dep[x])//这里应为1 << i,不是2 << i 
            {
                y = f[y][i];
            }
            if(dep[y] == dep[x])break;
        }
    if(x == y)return x;
    for(int i = 20;i >= 0;i--)
    {
        if(f[x][i] == f[y][i])continue;
        else x = f[x][i],y = f[y][i];
    }
    return fa[x];
}
int main()
{
    scanf("%d%d%d",&n,&m,&rt);
    int x,y;
    for(int i = 1;i < n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(rt,0,1);
    get(rt);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d
",lca(x,y));
    }
    return 0;
}