说明：CSDN和公众号文章同步发布，需要第一时间收到最新内容，请关注公众号【比特正传】。
最近公共祖先LCA是NOI大纲中指定的提高组的图论部分的知识点，难度系数为6，提高组考察难度为5~8。
引入
树是一种特殊的图，有没有想过一个问题，给你一棵多叉树，随机给出两个节点，求解两个节点的最近公共祖先？
模板题目链接：
https://www.luogu.com.cn/problem/P3379
基本概念
树的深度：给节点分层，根节点为第一层，即深度为1，依次类推，如图：
节点深度通过depth数组记录，如上图的depth数组如下:
朴素算法
Step1：先从根节点深搜整棵树，搜索过程中，填充深度数组depth和父节点数组fa，代码很简单，如下：
// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
depth[u] = depth[father]+1; // 当前节点深度等于父节点深度+1
fa[u] = father; // 记录u父节点
for(int ne : g[u]) { // 遍历所有孩子节点，并递归填充depth和fa数组
if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
}
}Step2：需要查询两个节点的最近公共祖先，最朴素的想法是，找出两个节点中，深度最大的那个节点，让其向上移动，直到两个节点的深度一样（即在同一层），此时停止，然后两个节点一起向上移动，直到两个节点的父节点为同一个节点即可得到最近公共祖先，代码如下：
// 寻找u和v的LCA
int lcaBaoli(int u, int v) {
if(depth[u] < depth[v]) swap(u, v); // 让u永远指向最深的节点
while(depth[u] > depth[v]) u = fa[u]; // 只要u的深度大于v，那就让u一直往上爬，直到两者在同一层停止就行
if(u == v) return u; // 在同一层了，先判断是不是同一个节点，如果是直接返回
while(fa[u] != fa[v]) { // u和v的父节点不是同一节点时
u = fa[u], v = fa[v]; // 让u和v一起向上爬，此时u和v一定处于同一层中
}
return fa[u]; // 此时u的父节点和v的父节点是同一个节点，因此直接返回即可
}
完整代码如下：
#include "bits/stdc++.h"
using namespace std;
const int N = 500000+9;
int n, m, s, x, y;
vector<int> g[N];
int depth[N]; // depth[u] 表示节点u的深度
int fa[N];
// 寻找u和v的LCA
int lcaBaoli(int u, int v) {
if(depth[u] < depth[v]) swap(u, v); // 让u永远指向最深的节点
while(depth[u] > depth[v]) u = fa[u]; // 只要u的深度大于v，那就让u一直往上爬，直到两者在同一层停止就行
if(u == v) return u; // 在同一层了，先判断是不是同一个节点，如果是直接返回
while(fa[u] != fa[v]) { // u和v的父节点不是同一节点时
u = fa[u], v = fa[v]; // 让u和v一起向上爬，此时u和v一定处于同一层中
}
return fa[u]; // 此时u的父节点和v的父节点是同一个节点，因此直接返回即可
}
// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
depth[u] = depth[father]+1; // 当前节点深度等于父节点深度+1
fa[u] = father; // 记录u父节点为father
for(int ne : g[u]) { // 遍历所有孩子节点，并递归填充depth和fa数组
if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
}
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for(int i=1; i<n; i++) {
scanf("%d%d", &x, &y);
g[x].push_back(y); // 建成无向图
g[y].push_back(x);
}
dfs(s, 0); // 通过深搜填充depth数组和p数组
while(m--) {
scanf("%d%d", &x, &y);
printf("%d\n", lcaBaoli(x, y));
}
return 0;
}结果如下：
以上思想有什么问题吗？哪里还可以优化呢？
还记得ST表吗？还记得并查集路径压缩吗？能不能把这些思想揉一揉，结合到一起呢？
RMQ问题之ST表_st表预处理时间复杂度-CSDN博客
算法思想
倍增思想
上面的代码问题是：向上找父亲，一层一层走太慢了，并查集如果不做路径压缩，也是一层一层找父亲，层数过大会导致效率贼低，因此并查集做了路径压缩。ST呢？f[i][j]表示起点为i，区间长度为2^j的区间，也就是区间[i, i+2^j -1] 的最值，那么递推式为：
f[i][j] = max(f[i][j-1], f[i+2^(j-1)][j-1])
是否可以借助该倍增思想求祖先，而不是一个一个往上跳。
注意：大于0的任何一个正整数，都可以用2的次幂求和表示出来（二进制），这句话非常重要
记录和保存下来每个节点的不同层级的祖先，按照距离进行划分，距离为1，表示上一级祖先（爸爸）；距离为2，表示上两级祖先（即爷爷）；距离为4，表示上四级祖先（即爷爷的爷爷）。
上面的想法可以通过fa数组进行保存，fa[u][i]表示u的【上2^i 级祖先】，上面的图对应的fa数组如下：
首先通过dfs深搜这棵树，搜索过程中填充depth和fa数组，代码如下，结合代码理解：
// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
depth[u] = depth[father]+1; // 当前节点深度等于父节点深度+1
fa[u][0] = father; // 当前节点向上2^0=1个祖先为当前的父节点
for(int i=1; i<=19; i++) { //向上找到1,2,4,8,....,2^19长度的祖先并填充
fa[u][i] = fa[fa[u][i-1]][i-1]; // 该递推式是核心
}
for(int ne : g[u]) { // 遍历所有孩子节点，并递归填充depth和p数组
if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
}
}上面的代码结合注释理解应该没什么问题。
下面看找最近公共祖先的核心代码，倍增算法:
// lcaMultiply 函数返回u和v的父节点
int lcaMultiply(int u, int v) { // 倍增
if(depth[u] < depth[v]) swap(u, v); // 让u指向深度最大的节点
for(int i=19; i>=0; i--) { // 向上找u的祖先，通过数学可以推出来，最终u和v的深度一定会相等，因为两者深度差为一个大于等于0的数，如果等于0什么都不做，对于大于0的数，一定可以通过1，2，4，8，16，32，...，凑出来
if(depth[fa[u][i]] >= depth[v]) {
u = fa[u][i];
}
}
if(u == v) return u; // 如果此时u和v刚好相等，那一定是最近的公共祖先，直接返回即可，
for(int i=19; i>=0; i--) { // 两个一起往上找祖先，
if(fa[u][i] != fa[v][i]) { // 如果两个祖先不一样，就继续往上走
u = fa[u][i]; // 向上走到祖先
v = fa[v][i];
}
}
return fa[u][0];
}完整代码如下：
#include "bits/stdc++.h"
using namespace std;
const int N = 500000+9;
int n, m, s, x, y;
vector<int> g[N];
int depth[N]; // depth[u] 表示节点u的深度
int fa[N][20]; // fa[u][i]表示节点u向上的2^i个父节点，比如000->111->222->333->444,则fa[444][0]为333，fa[444][1]为222, fa[444][2]为000
// lcaMultiply 函数返回u和v的父节点
int lcaMultiply(int u, int v) { // 倍增
if(depth[u] < depth[v]) swap(u, v); // 让u指向深度最大的节点
for(int i=19; i>=0; i--) { // 向上找u的祖先，通过数学可以推出来，最终u和v的深度一定会相等，因为两者深度差为一个大于等于0的数，如果等于0什么都不做，对于大于0的数，一定可以通过1，2，4，8，16，32，...，凑出来
if(depth[fa[u][i]] >= depth[v]) {
u = fa[u][i];
}
}
if(u == v) return u; // 如果此时u和v刚好相等，那一定是最近的公共祖先，直接返回即可，
for(int i=19; i>=0; i--) { // 两个一起往上找祖先，
if(fa[u][i] != fa[v][i]) { // 如果两个祖先不一样，就继续往上走
u = fa[u][i]; // 向上走到祖先
v = fa[v][i];
}
}
return fa[u][0];
}
// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
depth[u] = depth[father]+1; // 当前节点深度等于父节点深度+1
fa[u][0] = father; // 当前节点向上2^0=1个祖先为当前的父节点
for(int i=1; i<=19; i++) { //向上找到1,2,4,8,....,2^19长度的祖先并填充
fa[u][i] = fa[fa[u][i-1]][i-1]; // 该递推式是核心
}
for(int ne : g[u]) { // 遍历所有孩子节点，并递归填充depth和p数组
if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
}
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for(int i=1; i<n; i++) {
scanf("%d%d", &x, &y);
g[x].push_back(y); // 建成无向图
g[y].push_back(x);
}
dfs(s, 0); // 通过深搜填充depth数组和p数组
while(m--) {
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}
![[原型资源分享]经典产品饿了么UI模版部件库](https://img-blog.csdnimg.cn/img_convert/6b7960b2a54a3adfc7aa83948ad20583.png)
