ACM模板——LCA

深碍√TFBOYSˉ_ 2023-06-01 08:57 77阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define pb push_back
     6 #define maxn 500003
     7 typedef long long ll;
     8 using namespace std;
     9 
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0'); 
    24 }
    25 
    26 int N,M,S;
    27 vector<int> G[maxn];
    28 bool vis[maxn];
    29 int depth[maxn];
    30 int fa[maxn][22];
    31 void dfs(int u)
    32 {
    33     vis[u] = 1;
    34     _for(i,0,G[u].size())
    35         if(!vis[G[u][i]])
    36         {
    37             depth[G[u][i]] = depth[u]+1;
    38             fa[G[u][i]][0] = u; 
    39             dfs(G[u][i]);
    40         }
    41 }
    42 void bz()
    43 {
    44     _for(j,1,21)
    45         _for(i,1,N+1)
    46             fa[i][j] = fa[fa[i][j-1]][j-1];
    47 }
    48 int LCA(int u,int v)
    49 {
    50     //保证u深度较大 
    51     if(depth[u]<depth[v])
    52         swap(u,v);
    53     
    54     int dc = depth[u]-depth[v];
    55     _for(i,0,21) 
    56         if((1<<i)&dc)
    57             u = fa[u][i];
    58     
    59     if(u==v)    return u;
    60     _rep(i,20,-1)
    61         if(fa[u][i]!=fa[v][i])
    62             u = fa[u][i],v = fa[v][i];
    63     
    64     return fa[u][0];
    65 }
    66 int main()
    67 {
    68     N = read();
    69     M = read();
    70     S = read();
    71     _for(i,0,N-1)
    72     {
    73         int a = read();
    74         int b = read();
    75         G[a].pb(b);
    76         G[b].pb(a);
    77     }
    78     //求深度 和处理 fa 
    79     dfs(S); 
    80     bz();
    81     _for(i,0,M)
    82     {
    83         int a = read();
    84         int b = read();
    85         write(LCA(a,b));
    86         printf("\n");
    87     }
    88     return 0;
    89 }

倍增

转载于:https://www.cnblogs.com/Asurudo/p/11583655.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/5aad62bf55d94fda908ed86a63b0703d.png