最近公共祖先

倍增写法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,LOG=20;
int n,m,fa[N][LOG],dep[N];
vector<int> g[N];

void dfs(int u,int f){
    fa[u][0]=f;dep[u]=dep[f]+1;
    for(int k=1;k<LOG;k++)fa[u][k]=fa[fa[u][k-1]][k-1];
    for(int v:g[u])if(v!=f)dfs(v,u);
}

int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int k=LOG-1;k>=0;k--)if(dep[fa[u][k]]>=dep[v])u=fa[u][k];
    if(u==v)return u;
    for(int k=LOG-1;k>=0;k--)if(fa[u][k]!=fa[v][k])u=fa[u][k],v=fa[v][k];
    return fa[u][0];
}

int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
    dfs(1,0);
    while(m--){int u,v;cin>>u>>v;cout<<lca(u,v)<<"\n";}
}