LCA板子

模板题链接：

https://www.luogu.com.cn/problem/P3379

参考博客：

https://www.luogu.com.cn/blog/morslin/solution-p3379

代码：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
using namespace std;
const int MAXN=5e5+5;
int n,m,s;
int head[MAXN],tot1;
int dep[MAXN],f[MAXN][21],lg[MAXN];
struct node
{
    int to,next;
}e[MAXN*3];
void add(int x,int y)
{
    e[tot1].to=y;
    e[tot1].next=head[x];
    head[x]=tot1++;
}
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=lg[dep[u]];i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=fa)
            dfs(v,u);
    }
}
int lca(int a,int b)
{
    if(dep[a]<dep[b])
        swap(a,b);
    while(dep[a]>dep[b])
        a=f[a][lg[dep[a]-dep[b]]-1];
    if(a==b)return a;
    for(int k=lg[dep[a]]-1;k>=0;k--)
        if(f[a][k]!=f[b][k])
        a=f[a][k],b=f[b][k];
    return f[a][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(s,0);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d
",lca(x,y));
    }
    return 0;
}