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

LCA板子，动态数组和链式前向星两种存图版本，自取，代码参考MorsLin。

动态数组存图：

 1 #define dbg(x) cout<<#x<<" = "<< (x)<< endl
 2 #define IO std::ios::sync_with_stdio(0);
 3 #include <bits/stdc++.h>
 4 #define iter ::iterator
 5 using namespace  std;
 6 typedef long long ll;
 7 typedef pair<ll,ll>P;
 8 #define pb push_back
 9 #define se second
10 #define fi first
11 #define rs o<<1|1
12 #define ls o<<1
13 const ll inf=0x7fffffff;
14 const int N=5e5+10;
15 int n,m,s;
16 vector<int>g[N];
17 int d[N],lg[N],p[N][22];
18 void dfs(int u,int fa){
19     p[u][0]=fa;
20     d[u]=d[fa]+1;
21     for(int i=1;(1<<i)<=d[u];i++){
22         p[u][i]=p[p[u][i-1]][i-1];
23     }
24     for(int i=0;i<g[u].size();i++){
25         int v=g[u][i];
26         if(v==fa)continue;
27         dfs(v,u);
28     }
29 }
30 void init(){
31     for(int i=1;i<=n;i++){
32         lg[i]=lg[i-1]+((1<<lg[i-1])==i);
33     }
34     
35 }
36 int lca(int x,int y){
37     if(d[x]<d[y])swap(x,y);
38     while(d[x]>d[y]){
39         x=p[x][lg[d[x]-d[y]]-1];
40     }
41     if(x==y)return x;
42     for(int i=lg[x];i>=0;i--){
43         if(p[x][i]!=p[y][i]){
44             x=p[x][i];
45             y=p[y][i];
46         }
47     }
48     return p[x][0];
49 }
50 int main(){
51     //IO;
52     cin>>n>>m>>s;
53     for(int i=1;i<n;i++){
54         int x,y;
55         scanf("%d%d",&x,&y);
56         g[x].pb(y);
57         g[y].pb(x);
58     }
59     init();
60     dfs(s,0);
61     while(m--){
62         int x,y;
63         scanf("%d%d",&x,&y);
64         //cout<<lca(x,y)<<endl;
65         printf("%d
",lca(x,y));
66     }
67 }

前向星：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 struct yyy{
 5     int t,
 6         nex;
 7 }e[2*500001];
 8 int depth[500001],fa[500001][22],lg[500001],head[500001];
 9 int tot;
10 void add(int x,int y) //邻接表存树
11 {
12     e[++tot].t=y; 
13     e[tot].nex=head[x];
14     head[x]=tot;
15 }
16 void dfs(int f,int fath)
17 {
18     depth[f]=depth[fath]+1;
19     fa[f][0]=fath;
20     for(int i=1;(1<<i)<=depth[f];i++)
21       fa[f][i]=fa[fa[f][i-1]][i-1];
22     for(int i=head[f];i;i=e[i].nex)
23       if(e[i].t!=fath)
24         dfs(e[i].t,f);
25 }
26 int lca(int x,int y)
27 {
28     if(depth[x]<depth[y])
29       swap(x,y);
30     while(depth[x]>depth[y])
31       x=fa[x][lg[depth[x]-depth[y]]-1];
32     if(x==y)
33       return x;
34     for(int k=lg[depth[x]]-1;k>=0;k--)
35       if(fa[x][k]!=fa[y][k])
36         x=fa[x][k], y=fa[y][k];
37     return fa[x][0];
38 }
39 int n,m,s;
40 int main()
41 {
42     scanf("%d%d%d",&n,&m,&s);
43     for(int i=1;i<=n-1;i++)
44     {
45         int x,y;  scanf("%d%d",&x,&y);
46         add(x,y); add(y,x);
47     }
48     dfs(s,0);
49 
50     for(int i=1;i<=n;i++)
51       lg[i]=lg[i-1]+(1<<lg[i-1]==i);
52     for(int i=1;i<=m;i++)
53     {
54         int x,y;  scanf("%d%d",&x,&y);
55         printf("%d
",lca(x,y));
56     }
57 }