-
前言：
给定一个有根树,若节点\(z\)是两节点\(x,y\)所有公共祖先深度最大的那一个,则称\(z\)是\(x,y\)的最近公共祖先(\(Least Common Ancestors\))，简称\(LCA\).它在许多与树相关问题中发挥较大作用
-
怎么求
以这题为例:luogu P3379 【模板】最近公共祖先（LCA）
-
朴素暴力
让深度更大的节点\(x\)向上走至与另一节点\(y\)在同一深度上,然后同时向上走直至相遇.
时间复杂度 \(O(N)\)
代码略
-
倍增优化
按照上面的思路,但是不是一个一个走,而是先搜一遍树,预处理出\(x\)的第\(2^k (1<=2^k<=max(dep))\)个父亲,存起来.询问时,还是让深度更大的节点\(x\)向上倍增至与另一节点\(y\)在同一深度上,然后一起倍增向上跳
时间复杂度 \(O(M \log N)\)
代码见后
-
离线Tarjan
这个方法也通俗易懂：我们先将所有询问存起来，DFS一遍树同时我们把节点分为3类
已经回溯完的标记为\(''1''\)
正在dfs的及dfs过但未回溯的标记为\(''2''\)
然后在正在dfs的节点中处理与它有关的询问,若正在回溯已经DFS过的节点\(x\),有个询问是求\(LCA(x,y)\)。
若\(y\)的标记是\(''1''\),显然\(y\)第一个标记为\(''2''\)的祖先就为\(LCA(x,y)\)。万一标记不是\(''1''\)呢？比如当\(y\)是\(x\)祖宗还是没关系,在回溯到\(y\)时,\(y\)就是符合要求的答案
那怎么快速求第一个标记为\(''2''\)的祖先呢?用并查集维护一下就好了.
时间复杂度\(O(N+M)\)，较快然而只能离线
代码见后;
-
树链剖分
如果你不知道树剖的话可以去做做树剖模板或看这位大佬博客https://www.cnblogs.com/George1994/p/7821357.html
代码见后，给大家做个参考
时间复杂度\(O(M \log N)\)
-
倍增代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
#define ri register int
using namespace std;
const int maxn=500005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
struct Edge{
int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=0,t;
inline void add_edge(int f,int to){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
h[f]=num_edge;
return ;
}
int f[maxn][35],d[maxn];
int n,m,s;
void bfs(){
int u,v;
memset(d,0,sizeof(d));
queue <int>q;
q.push(s);d[s]=1;
//f[s][0]=s;
while(q.size()){
u=q.front();q.pop();
for(ri i=h[u];i;i=edge[i].ne){
v=edge[i].to;
if(d[v])continue;
f[v][0]=u,d[v]=d[u]+1;
//cout<<u<<' '<<v<<endl;
for(ri j=1;j<=t;j++)
{f[v][j]=f[f[v][j-1]][j-1];}//cout<<'8'<<f[v][j]<<endl;};
q.push(v);
}
}
return ;
}
inline int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
if(x==y)return x;
for(ri i=t;i>=0;i--){
if(d[f[x][i]]>=d[y])x=f[x][i];
}
//cout<<'*'<<x<<' '<<y<<endl;
if(x==y)return x;
for(ri i=t;i>=0;i--){
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int main(){
int x,y,z;
read(n),read(m),read(s);
memset(f,0,sizeof(f));
t=(int)(log(n)/log(2))+1;
for(ri i=1;i<n;i++){
read(x),read(y);
add_edge(x,y);
add_edge(y,x);
//cout<<x<<' '<<y<<endl;
}
bfs();
for(ri i=1;i<=m;i++){
read(x),read(y);
printf("%d\n",lca(x,y));
}
return 0;
}
- Tarjan代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <queue>
#include <map>
#define ll long long
#define ri register int
#define ull unsigned long long
using namespace std;
const int maxn=500005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int n,m,s,t;
struct Edge{
int ne,to;
}edge[maxn<<1];
struct QU{
int d,id;
QU(int x,int y){d=x,id=y;}
QU(){;}
};
vector <QU>q[maxn];
int h[maxn],num_edge=0,ans[maxn];
inline void add_edge(int f,int to){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
h[f]=num_edge;
return;
}
int fa[maxn],vis[maxn];
int get(int x){
if(fa[x]!=x)fa[x]=get(fa[x]);
return fa[x];
}
void dfs(int cur){
int u,v;
vis[cur]=1;
for(ri i=h[cur];i;i=edge[i].ne){
v=edge[i].to;
if(vis[v])continue;
dfs(v);
fa[v]=cur;//dfs后再合并
}
for(ri i=0;i<q[cur].size();i++){
u=q[cur][i].d,v=q[cur][i].id;
if(vis[u]==2){
ans[v]=get(u);
}
}
vis[cur]=2;//dfs过
return ;
}
int main(){
int x,y;
read(n),read(m),read(s);
for(ri i=1;i<n;i++){
read(x),read(y);
add_edge(x,y);
add_edge(y,x);
fa[i]=i;
}fa[n]=n;
for(ri i=1;i<=m;i++){
read(x),read(y);
//q[x].push_back(y);q[y].push_back(x);
q[x].push_back(QU(y,i));
q[y].push_back(QU(x,i));
}
dfs(s);
for(ri i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
- 树链剖分代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <map>
#include <queue>
#define ll long long
#define ri register int
using namespace std;
const int maxn=500005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
}
int n,m,s;
struct Edge{
int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=0;
inline void add_edge(int f,int to){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
h[f]=num_edge;
}
int dep[maxn],fa[maxn],size[maxn],top[maxn],son[maxn];//son--重儿子 top--重链顶端或轻链节点
void dfs_1(int u){
int v;
size[u]=1;
for(ri i=h[u];i;i=edge[i].ne){
v=edge[i].to;
if(dep[v])continue;
dep[v]=dep[u]+1,fa[v]=u;
dfs_1(v);
size[u]+=size[v];
if(!son[u]||size[son[u]]<size[v])son[u]=v;
}
return;
}
void dfs_2(int u,int t){//t--top重链起点
int v;
top[u]=t;
if(!son[u])return ;//叶子节点
dfs_2(son[u],t); //dfs重链上各节点
for(ri i=h[u];i;i=edge[i].ne){
v=edge[i].to;
if(v==fa[u])continue;
if(v!=son[u])dfs_2(v,v);//dfs下一条链的起点
}
return ;
}
int main(){
int x,y;
read(n),read(m),read(s);
for(ri i=1;i<n;i++){
read(x),read(y);
add_edge(x,y);
add_edge(y,x);
}
dep[s]=1;
dfs_1(s);
dfs_2(s,s);
for(ri i=1;i<=m;i++){
read(x),read(y);
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])y=fa[top[y]];
else x=fa[top[x]];
}//此时在一条链上
if(dep[x]>dep[y])swap(x,y);
printf("%d\n",x);
}
return 0;
}