洛谷P3379 【模板】最近公共祖先（LCA）——LCA

给一手链接 https://www.luogu.com.cn/problem/P3379

算是lca的模板吧

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

const int M=1e6+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int deep[M],f[M][],vis[M];

int n,m,S,first[M],cnt;

struct node{int to,next;}e[*M];

void ins(int x,int y){e[++cnt]=(node){y,first[x]}; first[x]=cnt;}

void dfs(int x){

    vis[x]=;

    for(int i=;(<<i)<=deep[x];i++) f[x][i]=f[f[x][i-]][i-];

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!vis[now]){

            deep[now]=deep[x]+;

            f[now][]=x;

            dfs(now);

        }

    }

}

int find(int x,int y){

    if(deep[x]<deep[y]) swap(x,y);

    int d=deep[x]-deep[y];

    for(int i=;(<<i)<=d;i++) if(d&(<<i)) x=f[x][i];

    if(x==y) return x;

    for(int i=;i>=;i--)

    if((<<i)<=deep[x]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

    return f[x][];

}

int main(){

    int x,y;

    n=read(); m=read(); S=read();

    for(int i=;i<n;i++) x=read(),y=read(),ins(x,y),ins(y,x);

    dfs(S);

    for(int i=;i<=m;i++) x=read(),y=read(),printf("%d\n",find(x,y));

    return ;

}