最近公共祖先
最近公共祖先简称LCA(Lowest Common Ancestor)。两个节点的最近公共祖先，就是这两个点所有的公共祖先里面，离根最远的那个。
- \(d(u,v)=h(u)+h(v)-2*h(lca(u,v))\)
例题
P3379 【模板】最近公共祖先（LCA）
Tarjan求解最近公共祖先
基本思路
1.dfs整棵树
2.每到达一个结点，先标记这个节点已被访问
3.随后遍历与该结点又访问关系的结点（记为z），若z已经被访问过，那么二者的lca就是getf(z)。
4.接着向孩子结点遍历，回溯的时候将孩子结点与当前结点用并查集合并。
参考代码
#include
using namespace std;
const int N=5e5+10;
vectornode[N];
int f[N];
int getf(int a){
return f[a]==a?a:f[a]=getf(f[a]);
}
int n,m,s;
int book[N];
struct{
int to,next;
}e[2*N];
int head[N],cnt;
inline void add(int a,int b){
e[++cnt].to=b;
e[cnt].next=head[a];
head[a]=cnt;
}
int ans[N];
void Tarjan(int s){
book[s]=1;
int to;
for(int i=head[s];i;i=e[i].next){
to=e[i].to;
if(book[to])ans[(i+1)/2]=getf(to);
}
for(auto i:node[s]){
if(book[i])continue;
Tarjan(i);
f[i]=s;
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
int a,b;
for(int i=1;i<=n;++i)f[i]=i;
for(int i=1;i 倍增
倍增是对朴素算法的优化。对于要求解的两个点a,b（假设a的深度大于b），先将两个结点上升到同一高度，然后再一起向上跳，这个过程用二进制就很快了。
参考代码
#include
using namespace std;
const int N=5e5+10;
const int M=5e5+10;
struct{
int to,next;
}e[2*M];
int head[N],cnt,dep[N];
int n,m,s;
inline void add(int a,int b){
e[++cnt].to=b;
e[cnt].next=head[a];
head[a]=cnt;
}
int len;
int fa[N][30];//fa[i][j]表示i结点的2^j个祖先
void dfs(int x,int f){
fa[x][0]=f;
dep[x]=dep[f]+1;
int to;
for(int i=1;(1<=0;--i){//这里可以直接理解为二分查找
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int main(){
scanf("%d%d%d",&n,&m,&s);
int a,b;
while((1< 基于DFS序的倍增
众所周知，可以很快的判断出两个节点的祖孙关系。
我们只需将深度大的点一直向上跳(还是基于二进制或二分的思想跳)，并不断判断祖孙关系即可。
这种方法不用将两个点升到同一高度，并且常数更小。
参考代码
#include
using namespace std;
const int N=5e5+10;
const int M=5e5+10;
struct{
int to,next;
}e[2*M];
int head[N],cnt,dep[N];
int n,m,s;
inline void add(int a,int b){
e[++cnt].to=b;
e[cnt].next=head[a];
head[a]=cnt;
}
int len;
int fa[N][30];
int dfn[N],se[N],ti;
void dfs(int x,int f){
fa[x][0]=f;
dep[x]=dep[f]+1;
int to;
dfn[x]=++ti;
se[x]=1;
for(int i=1;(1<=dfn[a])return b;
for(int i=len;i>=0;--i){
int na=fa[a][i];
if(!na)continue;//这个地方小心跳穿了
if(!(dfn[na]<=dfn[b]&&dfn[na]+se[na]-1>=dfn[b]))
a=na;
}
return fa[a][0];
if(a==b)return a;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
int a,b;
while((1<