【模板】最近公共祖先（LCA）

题意

给一个树，然后多次询问(a,b)的LCA

模板(主要参考一些大佬的模板)

#include
    
     //自己的2点:树的邻接链表(静态)表示; lca 的倍增算法//优化 log[]const int maxn=500010;int N,M,S;//S根节点标号int head[maxn];//head[i]=k 以i为起点的第一条边是edge[k]int dep[maxn],dp[maxn][21];//dp[i][j] i向上走2^jint lg[maxn];//(log2(i)+1)struct edge{    int v,next;};edge egs[maxn<<1];int k=0;void getlg(){    for(int i=1;i<=n;i++){        lg[i]=lg[i-1]+((1<
     
      =dep[b] a 向上走    for(int j=20;j>=0;j--){        if(dep[a]-(1<
      
       =dep[b]){            a=dp[a][j];        }    }    if(a==b) return a;    //a,b同时向上走    for(int i=20;i>=0;i--){        if(dp[a][i]!=dp[b][i]){            a=dp[a][i];            b=dp[b][i];        }    }    return dp[a][0];}int main(){    scanf("%d %d %d",&N,&M,&S);    memset(head,-1,sizeof(head));    memset(dep,0,sizeof(dep));    memset(dp,0,sizeof(dp));    for(int i=1;i

加了lg[]数组优化的(略微快一点)

#include
    
     //自己的2点:树的邻接链表(静态)表示; lca 的倍增算法//优化 log[]const int maxn=500010;int N,M,S;//S根节点标号int head[maxn];//head[i]=k 以i为起点的第一条边是edge[k]int dep[maxn],dp[maxn][21];//dp[i][j] i向上走2^jint lg[maxn];//(log2(i)+1)struct edge{    int v,next;};edge egs[maxn<<1];int k=0;void getlg(){    for(int i=1;i<=N;i++){        lg[i]=lg[i-1]+((1<
     
      =dep[b] a 向上走    while(dep[a]>dep[b]){        a=dp[a][lg[dep[a]-dep[b]]-1];    }    if(a==b) return a;    //a,b同时向上走    for(int i=(lg[dep[a]]-1);i>=0;){        if(dp[a][i]!=dp[b][i]){            a=dp[a][i];            b=dp[b][i];            i=lg[dep[a]];        }        else i--;    }    return dp[a][0];}int main(){    scanf("%d %d %d",&N,&M,&S);    memset(head,-1,sizeof(head));    memset(dep,0,sizeof(dep));    memset(dp,0,sizeof(dp));    getlg();    for(int i=1;i