目录
LCA最近公共祖先
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
暴力求解太慢，这里先摘记一种做法-倍增法。
对于每一个节点，我们先通过dfs预先处理出当前节点向根移动2的幂次方的节点编号(有种st表的感觉)。转移方程：\(fa[u][i]=fa[fa[u][i-1]][i-1],i\ge 1\)
关键数组：深度数组dep和父节点？数组fa
void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;
for(int i=1;i<=N;++i){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=head[x];i;i=p[i].next){
if(p[i].to!=f) dfs(p[i].to,x);
}
return;
}
对于询问，首先让u与v处于同一深度，此处排除当前u和v即为最近公共祖先的情况。之后让u和v一起向根节点游，\(fa[u][i]!=fa[v][i]\)，则继续向上游。直到最后答案为\(fa[v][0]\)
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);//使u深度大
for(int i=N;i>=0;--i){
if(dep[fa[u][i]]>=dep[v]){//为了处于同一深度
u=fa[u][i];
}
}
if(u==v) return v;//当前节点即为最近公共祖先
for(int i=N;i>=0;--i){
if(fa[u][i]!=fa[v][i]){//一起向上
u=fa[u][i];
v=fa[v][i];
}
}
return fa[v][0];
}
例题
模板题
//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*f;
}
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
最近公共祖先模板题
利用深搜构造lca数组
*/
const int maxm=5e5+5,inf=0x3f3f3f3f,mod=998244353,N=20;
int n,m,s,cnt=1,head[maxm],dep[maxm],fa[maxm][N+1];
struct node{
int to,next;
}p[maxm<<1];
void add_edge(int a,int b){
p[cnt].to=b;
p[cnt].next=head[a];
head[a]=cnt++;
return ;
}
void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;
for(int i=1;i<=N;++i){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=head[x];i;i=p[i].next){
if(p[i].to!=f) dfs(p[i].to,x);
}
return;
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=N;i>=0;--i){
if(dep[fa[u][i]]>=dep[v]){
u=fa[u][i];
}
}
if(u==v) return v;
for(int i=N;i>=0;--i){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
return fa[v][0];
}
void solve(){
cin>>n>>m>>s;
int a,b;
for(int i=1;i<n;++i){
cin>>a>>b;
add_edge(a,b);
add_edge(b,a);
}
dfs(s,0);
while(m--){
cin>>a>>b;
cout<<lca(a,b)<<'\n';
}
return ;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _=1;
// cin>>_;
while(_--){
solve();
}
return 0;
}
根据题意抽象为树，再利用倍增优化。具体代码与lca模板题巨像
代码：
链式前向星 qiansui_code
邻接表 qiansui_code
综合题
- 找树上加边所构成环的最大边权值 2023ACM暑假训练day 10 树上问题 - F
- 节点附加颜色条件，求移动最短时间 2023牛客多校第三场 I 难题 hrad hard hard
相关资料
整体介绍
https://oi-wiki.org/graph/lca/
模板及视频讲解：
倍增法 https://www.cnblogs.com/dx123/p/16320461.html