一、概念【最近公共祖先】最近公共祖先简称LCALowest Common Ancestor。两个节点的最近公共祖先就是这两个点的公共祖先里面离根最远的那个。多个点的最近公共祖先也是同理。二、性质【性质】一个点的最近公共祖先是自己LCA(x) x如果 x 是 y 的祖先那么 LCA(x,y) x如果 x 和 y 并不是对方的祖先那么 x,y 分别位于 LCA(x,y) 的两棵不同的子树中记 S 为树中的点集。前序遍历中LCA(S) 出现在所有 S 之前后序遍历中LCA(S) 出现在所有 S 之后LCA(x,y) 一定在 (x,y) 之间的简单路径上记 A, B 为树中的两个点集那么 LCA(A U B) LCA(LCA(A), LCA(B))d(x,y) d(r,x) d(r,y) - 2 * d(r,LCA(x,y))其中 d 是两点间距离r 表示根节点。三、解法1. 朴素解法【算法原理】向上标记法让两个点分别向上走同时标记行走的结点第一次相遇的位置就是想要求的 LCA。【时间复杂度】如果没有告知父结点那么需要 dfs 预处理所有结点的父结点时间复杂度为 O(n)。每次查询两点的最近公共祖先时间复杂度为 O(n)。如果是多次查询效率较差。模板题P3884 [JLOI2009] 二叉树问题 - 洛谷#includeiostream #includevector #includequeue using namespace std; const int N 110; vectorint edge[N]; int fa[N]; int dist[N]; int x, y; int dfs(int u) { int ret 0; for(auto e : edge[u]) { ret max(ret, dfs(e)); } return ret 1; } int bfs() { queueint q; q.push(1); int ret 0; while(q.size()) { int sz q.size(); ret max(ret, sz); while(sz--) { int v q.front(); q.pop(); for(auto e : edge[v]) { q.push(e); } } } return ret; } int main() { int n; cin n; for(int i 1; i n; i) { int u, v; cin u v; //u - v edge[u].push_back(v); fa[v] u; } cin x y; while(x ! 1) { dist[fa[x]] dist[x] 1; x fa[x]; } int len 0; while(y ! 1 dist[y] 0) { y fa[y]; len; } cout dfs(1) endl; cout bfs() endl; cout 2 * dist[y] len endl; return 0; }2. 树上倍增【树上倍增】利用倍增的思想优化朴素解法优化方式与 ST 表非常像本质上是动态规划。【算法原理】用倍增思想预处理一些信息状态表示 f[x][i]结点 x 向上走 2^i 步之后能够走到的结点dep[x]结点 x 所在的深度也就是距离根节点的距离再加1状态转移方程 f[x][i] f[f[x][i-1]][i-1]很容易理解结点 x 向上走 2^(i-1) 步之后再向上走 2^(i-1) 步能够走到的结点dep[x] dep[fa]1父结点的深度再加一初始化 f[x][0] fa。代码实现const int N 5e5 10, M 25; vectorint edges[N]; int f[N][M], dep[N]; void dfs(int x, int fa) { f[x][0] fa; dep[x] dep[fa] 1; // 更新这个结点的 f 表 for(int i 1; i 20; i) f[x][i] f[f[x][i - 1]][i - 1]; for(int y : edges[x]) { if(y fa) continue; dfs(y, x); } }使用预处理的信息让 x 向上爬到深度为 k 层 利用二进制表示凑出两者高度的差值若 k10x 所在的层数为 30那么需要向上跳 20 步20 的二进制表示为 10100那么依次向上跳 16,4 步即可。代码实现// 让 x 向上跳到第 k 层 void up(int x, int k) { for(int i 20; i 0; i--) if(dep[f[x][i]] k) x f[x][i]; }使用预处理的信息查询 x,y 的 LCA先让较低的点向上爬到与较高点同层然后两者一起向上爬直到爬到两者 LCA 的下一层为止。代码实现int lca(int x, int y) { if(dep[x] dep[y]) swap(x, y); // 让 x 跳到 y 的层数 for(int i 20; i 0; i--) if(dep[f[x][i]] dep[y]) x f[x][i]; // 如果已经同层不用跳了 if(x y) return x; // 一起跳到 lca 的下一层 for(int i 20; i 0; i--) { if(f[x][i] ! f[y][i]) { x f[x][i]; y f[y][i]; } } return f[x][0]; }时间复杂度预处理的时间为 O(nlog n)每次查询的时间为 O(log n)。模板题P3379 【模板】最近公共祖先LCA - 洛谷代码#include bits/stdc.h using namespace std; #define endl \n #define int long long const int mod 1e9 7; const int MOD 998244353; const int N 5e5 10; const int M 25; int n, m, s; vectorint edges[N]; int f[N][M]; int dep[N]; // 初始化 void dfs(int x, int fa) { f[x][0] fa; dep[x] dep[fa] 1; for(int i 1; i 20; i) f[x][i] f[f[x][i - 1]][i - 1]; for(auto y : edges[x]) { if(y fa) continue; dfs(y, x); } } int lca(int x, int y) { // x - 与y同层 if(dep[x] dep[y]) swap(x, y); for(int i 20; i 0; i--) { if(dep[f[x][i]] dep[y]) { x f[x][i]; } } if(x y) return x; // x, y 一起跳跳到lca的下方 for(int i 20; i 0; i--) { if(f[x][i] ! f[y][i]) { x f[x][i]; y f[y][i]; } } return f[x][0]; } void solve() { cin n m s; for(int i 1; i n - 1; i) { int x, y; cin x y; edges[x].emplace_back(y); edges[y].emplace_back(x); } dfs(s, 0); while(m--) { int a, b; cin a b; cout lca(a, b) endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }3. Tarjan算法【算法原理】最近公共祖先的性质如果 x 是 y 的祖先那么 LCA(x,y)x如果 x 和 y 并不是对方的祖先那么 x,y 分别位于 LCA(x,y) 的两棵不同的子树中记 S 为树中的点集。前序遍历中LCA(S) 出现在所有 S 之前后序遍历中LCA(S) 出现在所有 S 之后。Tarjan 算法是一种离线算法巧妙地利用 dfs 的时序结合并查集快速找出一批查询的公共祖先。设若干查询的最近公共祖先为 u当我们在递归遍历以 u 为根的子树时从某个点向上回溯之后把这个点所在的集合合并到父亲节点所在的集合中递归完以某个结点为根的所有子树从某个点回溯之前看看与它相关的查询操作如果查询的另外一个点已经遍历过另外一个点所在集合的代表元素就是两者的 lca。【代码实现】准备工作vectorint edges[N]; // 存树 vectorPII query[N]; // 存问题q[x] 表示结点包含 x 的所有查询以及问题编号 int fa[N]; // 并查集 bool st[N]; // 标记 dfs 过程中哪些点已经遍历过 int ret[N]; // 每次查询的结果离线所有查询操作void fun() { cin n m s; for(int i 1; i n; i) fa[i] i; // 初始化并查集 for(int i 1; i n; i) // 读入树的边 { int a, b; cin a b; edges[a].push_back(b); edges[b].push_back(a); } for(int i 1; i m; i) // 离线所有查询为了统计最终结果因此需要记录问题的编号 { int a, b; cin a b; query[a].push_back({b, i}); query[b].push_back({a, i}); } }算法流程从根节点开始 dfs进入 x 时打上已经遍历的标记st[x]true枚举 x 的孩子 y如果没有访问过遍历 y。回溯时将 y 这个子树上的点合并到 x 上fa[y]x递归完以 x 为根的子树向上回溯时更新结果。枚举以 x 为起点的查询 (x,y)a. 如果 y 被搜索过则 y 所在并查集的根结点就是 x,y 的 LCAb. 如果 y 没有被访问过那么这个查询会在遍历到 y 结点的时候再去更新结果。void tarjan(int x) { st[x] true; for(auto y : edges[x]) { if(st[y]) continue; tarjan(y); fa[y] x; } // 处理查询 for(auto t : query[x]) { int y t.first, i t.second; if(st[y]) ret[i] find(y); } }补充代码里还需要并查集的find函数路径压缩int find(int x) { if(fa[x] ! x) fa[x] find(fa[x]); return fa[x]; }模板题P3379 【模板】最近公共祖先LCA - 洛谷代码#include bits/stdc.h using namespace std; #define endl \n #define int long long const int mod 1e9 7; const int MOD 998244353; const int N 5e5 10; vectorint edges[N]; vectorpairint, int query[N]; bool st[N]; int ret[N], fa[N]; int n, m, s; int find(int x) { return x fa[x] ? x : fa[x] find(fa[x]); } void tarjan(int x) { st[x] true; for(auto y : edges[x]) { if(st[y]) continue; tarjan(y); fa[y] x; } for(auto e : query[x]) { if(st[e.first]) { ret[e.second] find(e.first); } } } void solve() { cin n m s; for(int i 1; i n; i) fa[i] i; for(int i 1; i n; i) { int x, y; cin x y; edges[x].emplace_back(y); edges[y].emplace_back(x); } for(int i 1; i m; i) { int x, y; cin x y; query[x].push_back({y, i}); query[y].push_back({x, i}); } tarjan(s); for(int i 1; i m; i) { cout ret[i] endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }