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

嗯...

题目链接：https://www.luogu.com.cn/problem/P3379

这道题是LCA模板，我用的是倍增的思想。

首先要先用dfs对up和dep进行初始化：

up[u][0]=fa; up[u][k]=up[up[u][k-1]][k-1];
//类似分步走的思想
dep[u]=dep[fa]+1;

然后进行倍增：

1.要让u，v跳到同一高度。

2.一起跳到公共祖先。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn=500005;
 7 
 8 int n,m,s,tot;
 9 int up[maxn][30],dep[maxn],head[maxn];
10 
11 struct node{
12     int to,next;
13 } e[maxn*2];
14 
15 inline void add(int u,int v){
16     e[++tot].to=v;
17     e[tot].next=head[u];
18     head[u]=tot;
19 }
20 
21 inline void dfs(int u,int fa){
22     up[u][0]=fa; dep[u]=dep[fa]+1;
23     for(int k=1;(1<<k)<=dep[u];k++)
24         up[u][k]=up[up[u][k-1]][k-1];
25     for(int i=head[u];i!=-1;i=e[i].next)
26         if(e[i].to!=fa) dfs(e[i].to,u);
27 }//dfs预处理 
28 
29 inline int lca(int u,int v){
30     if(dep[u]<dep[v]) swap(u,v);
31     if(dep[u]!=dep[v])
32         for(int k=20;k>=0;k--)
33             if(dep[up[u][k]]>=dep[v])
34                 u=up[u][k];//让u和v到同一高度 
35     if(u==v) return u;
36     for(int k=20;k>=0;k--)
37         if(up[u][k]!=up[v][k])
38             u=up[u][k],v=up[v][k];//一起向上倍增 
39     return up[u][0];
40 }
41 
42 int main(){
43     memset(head,-1,sizeof(head));
44     scanf("%d%d%d",&n,&m,&s);
45     for(int i=1;i<n;i++){
46         int u,v;
47         scanf("%d%d",&u,&v);
48         add(u,v); add(v,u);
49     }
50     dfs(s,0);
51     for(int i=1;i<=m;i++){
52         int u,v;
53         scanf("%d%d",&u,&v);
54         printf("%d
",lca(u,v));
55     }
56     return 0;
57 }

AC代码