倍增求LCA

青旅半醒 2021-10-26 18:31 229阅读 0赞

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<cstdlib>
     5 #include<cmath>
     6 #include<algorithm>
     7 using namespace std;
     8 #define maxn 500010
     9 
    10 int n, m, tot, s, t;
    11 int fa[maxn][22],first[maxn],deep[maxn];
    12 struct edge{
    13     int nextx,to;
    14 }e[maxn<<1];
    15 
    16 void add(int u,int v)
    17 {
    18     tot++;
    19     e[tot].nextx=first[u];
    20     first[u]=tot;
    21     e[tot].to=v;
    22 }
    23 
    24 void dfs(int x,int f,int depth)
    25 {
    26     deep[x]=depth;
    27     fa[x][0]=f;
    28     for(int i=first[x];i;i=e[i].nextx)//双层循环嵌套，注意i，j使用
    29     {
    30         int u=e[i].to;
    31         if(u==f)continue;
    32         fa[u][0]=x;
    33         for (int j = 1; j <= t;j++)//从1开始，i-1不能为0
    34             fa[u][j] = fa[fa[u][j - 1]][j - 1];//对u进行操作，而不是x
    35         dfs(u, x, depth + 1);
    36     }
    37 }
    38 
    39 
    40 int get_lca(int x,int y)
    41 {
    42     if(deep[x]<deep[y])swap(x,y);
    43     for(int i=t;i>=0;i--)//此处循环从0开始，使得其可以只跳一步,且必须为倒序
    44         if(deep[fa[x][i]]>=deep[y])
    45             x=fa[x][i];
    46     if(x==y)return x;
    47     for(int i=t;i>=0;i--)//从0开始，理由同上，必须为倒序
    48         if(fa[x][i]!=fa[y][i])
    49             x=fa[x][i],y=fa[y][i];
    50     return fa[x][0];
    51 }
    52 
    53 int main()
    54 {
    55     scanf("%d%d%d",&n,&m,&s);
    56     for(int i=1;i<=n-1;i++)
    57     {
    58         int a,b;
    59         scanf("%d%d",&a,&b);
    60         add(a,b),add(b,a);
    61     }
    62     t = log2(n) + 1;//此处属于优化
    63     dfs(s,s,1);
    64     for(int i=1;i<=m;i++)
    65     {
    66         int a,b;
    67         scanf("%d%d",&a,&b);
    68         cout<<get_lca(a,b)<<"\n";
    69     }
    70     return 0;
    71 }

转载于:https://www.cnblogs.com/KGW-/p/11229057.html