【模板】最近公共祖先（LCA）
题意
模板(主要参考一些大佬的模板)
#include<bits/stdc++.h>
//自己的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^j
int 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<<lg[i-1])==i);
}
}
void add(int a,int b){
//加入边a,b
egs[k].v=b;
egs[k].next=head[a];
head[a]=k++;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
//printf("db: u %d fa %d dep %d %d\n",u,fa,dep[u],dep[fa]);
dp[u][0]=fa;
for(int i=1;(1<<i)<=dep[u];i++){
dp[u][i]=dp[dp[u][i-1]][i-1];
}
int k;
for(k=head[u];k!=-1;k=egs[k].next){
if(egs[k].v!=fa) dfs(egs[k].v,u);
}
}
int lca(int a,int b){
if(dep[a]<dep[b]) std::swap(a,b);
//dep[a]>=dep[b] a 向上走
for(int j=20;j>=0;j--){
if(dep[a]-(1<<j)>=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<N;i++){
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
dfs(S,0);
/*
for(int i=0;i<=N;i++){
printf("db: %d %d\n",i,dep[i]);
}
*/
int x,y;
for(int i=1;i<=M;i++){
scanf("%d %d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
加了lg[]数组优化的(略微快一点)
#include<bits/stdc++.h>
//自己的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^j
int 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<<lg[i-1])==i);
}
}
void add(int a,int b){
//加入边a,b
egs[k].v=b;
egs[k].next=head[a];
head[a]=k++;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
//printf("db: u %d fa %d dep %d %d\n",u,fa,dep[u],dep[fa]);
dp[u][0]=fa;
for(int i=1;i<=(lg[dep[u]]-1);i++){
dp[u][i]=dp[dp[u][i-1]][i-1];
}
int k;
for(k=head[u];k!=-1;k=egs[k].next){
if(egs[k].v!=fa) dfs(egs[k].v,u);
}
}
int lca(int a,int b){
if(dep[a]<dep[b]) std::swap(a,b);
//dep[a]>=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<N;i++){
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
dfs(S,0);
/*
for(int i=0;i<=N;i++){
printf("db: %d %d\n",i,dep[i]);
}
*/
int x,y;
for(int i=1;i<=M;i++){
scanf("%d %d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
值得注意的问题
- 初始化的位置
- 树的邻接链表表示(真的比较省内存而且好用)
- lca的倍增算法(还可以求树上两点距离)