最近公共祖先（LCA）
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
-----oi wiki
举个例子
在这张图中，\(5\) 和 \(9\) 的最近公共祖先就是 \(3\)，\(9\) 和 \(7\) 的最近公共祖先就是 \(2\)
由于在树上两点间的简单路径是唯一的，并且从上图中我们可以很容易发现两点的 LCA 一定在其的简单路径上，所以我们有时候需要求出某两个点的 LCA
P3379 【模板】最近公共祖先（LCA）
以下所有的测试数据输入输出皆保持一致
暴力跳
最暴力的算法一个一个往上跳，复杂度 \(O(TLE)\)
没写，因为会 T
倍增求 LCA
这个方法是最简单也是最好想的一个方法，而且支持在线的查询，时间复杂度为 \(O(m\log n)\)，本人看来是暴力的一个优化
我们维护一个 \(f[i][j]\) 数组表示 \(i\) 点往上跳 \(2^{j}\) 所到达的点的编号，\(dep[i]\) 表示 \(i\) 号点在树中的深度
我们首先要做的就是 DFS 一遍把我们的 \(f\)，\(dep\) 数组求出来，然后在查询的时候，按照下面的步骤：
我们首先判断两个点的深度大小，保证传入的 \(x\) 的深度大于 \(y\) 的深度
我们让 \(x\) 点开始往上跳，从大到小枚举 \(f\) 数组的第二维，只要跳完之后深度大于等于 \(y\) 的深度就跳，这样最后我们使 \(x\) 和 \(y\) 来到了同一高度。
我们让 \(x\) 和 \(y\) 一起向上跳，前提是两点跳完后不在同一位置，因为跳的时候可能会跳超，但是两点的编号相同，造成是公共祖先但不是最近的情况，最后我们得到了两点的最近公共祖先下方的两个点 \(x'\) 和 \(y'\)，这个时候直接返回其中一个的父节点即可。
注意第二步完成之后需要特判一下，是否两点编号相等，相等直接返回即可，防止两点在同一链上的情况
code：
#include<bits/stdc++.h>
#define N 500010
using namespace std;
struct sb{int t,nex;}e[N<<1];//t存放终点，nex存放下一个边
int head[N],tot;//head存放头节点，tot存放建边数量
int de[N],f[N][22],lg[N];//de存放每一个点的深度，f存放每一个点第2的i次方的祖先，lg存放log值
inline void add(int x,int y)//存边函数
{
e[++tot].t=y;//存放终点
e[tot].nex=head[x];//存放下一个边的头节点
head[x]=tot;//更新
}
inline void dfs(int now,int fa)//深搜函数
{
f[now][0]=fa;//当前节点上一个祖先就是fa
de[now]=de[fa]+1;//当前节点的深度就是祖先的深度加一
for(int i=1;i<=lg[de[now]];i++)//从2的1次方开始循环
f[now][i]=f[f[now][i-1]][i-1];//当前点的第2的i次方个祖先就是从当前的点的第i-1次方祖先的2的i-1次方的祖先
for(int i=head[now];i;i=e[i].nex)//寻找和当前点相连的点
if(e[i].t!=fa)dfs(e[i].t,now);//如果终点不是祖先的话就继续深搜
}
inline int LCA(int x,int y)//寻找最近公共祖先
{
if(de[x]<de[y])swap(x,y);//如果x的深度小于y的深度就把xy的值互换
while(de[x]>de[y])//只要x的深度大于y
x=f[x][lg[de[x]-de[y]]-1];//先让x跳到和y一样的深度
if(x==y)return y;//如果两个点相等说明y是x的祖先，直接返回y
for(int k=lg[de[x]];k>=0;k--)
{
if(f[x][k]==f[y][k])continue;//因为是跳到LCA下面的一层，所以他们一定不相等，
x=f[x][k],y=f[y][k];//替换xy的值继续循环
}
return f[x][0];//返回当前x的祖先即为最近公共祖先
}
int main()
{
int n,m,d;//n个点，m次询问，d为根节点
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=n-1;i++)//从第一个到最后一个
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);//存边
add(y,x);//无向图存两次
}
for(int i=1;i<=n;i++)//预处理log的值
lg[i]=lg[i-1]+(1<<lg[i-1]==i);//计算
dfs(d,0);//深搜处理出f和de的值
for(int i=1;i<=m;i++)//开始询问
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));//输出最近公共祖先
}
return 0;//好习惯
}
tarjan 求 LCA
这个算法在 \(n,m\) 差不多的时候是比较快的，因为他复杂度是 \(O(n+m)\) 的，可惜的是只能离线。
我们对于每一个询问的两点之间连一条无向边（并不是在存树的数组里面连边）
在 DFS 的过程中，给走过的节点打上标记，同时维护并查集，如果 \(u\) 节点的这棵子树没搜完，那么 \(fa[u] = u\);，搜完后再更新并查集。
我们假设查询 \(u\) 和 \(v\) 的最近公共祖先，搜到节点 \(u\)，如果另一个节点 \(v\) 已经被搜到过了，那么 \(v\) 点的并查集祖先就是 \(u\) 和 \(v\) 的最近公共祖先。
我们来模拟一下用 tarjan 求 LCA 的样例
我们在 DFS 的时候，首先来到 \(4\) 号点，然后我们 \(vis[4]=1\)，将两个子节点都合并到 \(4\) 号点上，发现有一组询问 \(4,5\) 但是 \(vis[5]=0\) 所以不能确定 LCA
然后来到 \(2\)，将 \(vis[2]=1\) 发现没法往下走，所以不走了，发现有 \((3,2)\) 和 \((1,2)\) 两组询问，但 \(vis[3]=0\)，\(vis[1]=0\) 所以不能确定 LCA
然后来到 \(1\)，将 \(vis[1]=1\)，将子节点合并到 \(1\) 号点，发现有询问 \((1,2)\)，这个时候 \(vis[2]=1\) 所以我们能确定 LCA，直接返回 \(fid(2)\)，也就是 \(4\)
然后来到 \(3\)，将 \(vis[3]=1\)，没有子节点，发现有询问 \((3,2)(3,5)\)，这时候 \(vis[2]=1,vis[5]=0\)，所以能确定第一个询问的 LCA，记录 LCA\((3,2)=fid(2)=4\)
然后来到 \(5\)，将 \(vis[5]=1\)，发现有询问 \((3,5)(4,5)\)，我们发现两个都可以确定，记录 LCA\((3,5)=fid(3)=1\)， LCA\((4,5)=fid(4)=4\)
至此算法结束。
有的人可能会问，要是出现下面的情况怎么办？
要是查 \((1,2)\) 的话，不就会返回 \(fid(2)\) 递归下去不就是 \(6\) 了吗？
注意我们是在子树全遍历完才会修改当前点的 \(f\) 的值，所以不会出现这个情况
code：
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 2000100
using namespace std;
int n,m,s,fa[N],vis[N],head[N],cnt,Head[N],cnt1=1;
struct sb{int u,v,next,lca;}e[N],e1[N];
inline void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}
inline void Add(int u,int v){e1[++cnt1].v=v;e1[cnt1].next=Head[u];Head[u]=cnt1;}
inline int fid(int x){if(fa[x]==x)return x;return fa[x]=fid(fa[x]);}
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void DFS(int x,int f)
{
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].v;
if(v==f)continue;
if(!vis[v])DFS(v,x),fa[v]=x;
}
for(int i=Head[x];i;i=e1[i].next)
{
int v=e1[i].v;
if(vis[v])e1[i].lca=e1[i^1].lca=fid(v);
}
}
signed main()
{
n=read(),m=read(),s=read();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n-1;i++)
{
int u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
Add(u,v);
Add(v,u);
}
DFS(s,0);
for(int i=2;i<=cnt1;i+=2)
cout<<e1[i].lca<<endl;
return 0;
}
/*
6 1 6
6 4
3 1
2 4
5 1
1 4
1 2
*/
树链剖分
推销自己的博客
以后我会重修的
首先我们就是要进行两遍 dfs 把 \(dep,f,siz,son,top\) 数组给处理出来，他们分别表示当前点的深度，当前点的父节点，以当前点为根的子树大小，当前点的重儿子编号，当前点所在的链的链头元素。
我们处理完之后，我们根据两点的深度大小来往上跳，和倍增一样，我们要防止跳超了，所以跳完以后两个点的 \(top\) 数组相等就说明已经有一个点的链头元素为两个点的 LCA，然后我们直接返回即可。
注意在跳的时候并不用保证谁比谁深度大，因为跳的时候是两个交替着跳，所以没必要
code：
#include <bits/stdc++.h>
#define N 1000100
#define endl '\n'
using namespace std;
struct sb{int u,v,next;}e[N];
int dep[N],fa[N],siz[N],head[N],son[N],rt,n,m,cnt,top[N];
inline void add(int u,int v){e[++cnt].u=u;e[cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void dfs1(int x,int deep,int f)
{
dep[x]=deep;fa[x]=f;siz[x]=1;
int maxn=-1;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].v!=f)
{
dfs1(e[i].v,deep+1,x);
siz[x]+=siz[e[i].v];
if(siz[e[i].v]>maxn)maxn=siz[e[i].v],son[x]=e[i].v;
}
}
return ;
}
inline void dfs2(int x,int tp)
{
top[x]=tp;
if(!son[x])return ;
dfs2(son[x],tp);
for(int i=head[x];i;i=e[i].next)
if(e[i].v!=fa[x]&&e[i].v!=son[x])dfs2(e[i].v,e[i].v);
return ;
}
inline int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
signed main()
{
n=read();m=read(),rt=read();
for(int i=1;i<=n-1;i++)
{
int u=read(),v=read();
add(u,v);add(v,u);
}
dfs1(rt,0,rt);
dfs2(rt,rt);
for(int i=1;i<=m;i++)cout<<LCA(read(),read())<<endl;
return 0;
}
其他算法
由于本人实在太弱所以只整理了前面的三种
其实也可以用 DFS 序来求 LCA，可以去看看魏老师的博客：https://www.luogu.com.cn/blog/AlexWei/leng-men-ke-ji-dfs-xu-qiu-lca
也可以用欧拉序来求 LCA，比如：https://www.luogu.com.cn/blog/shenhy1205/solution-p3379
或者转化为 RMQ 问题求解：https://www.cnblogs.com/cj-xxz/p/11142232.html
或者用 LCT ：https://www.luogu.com.cn/blog/surf/solution-p3379
