c++基础树上问题——求lca（最近公共祖先）的几种方法，算法必看哟！

要求lca，就应先求出每个点的深度（用dfs），用朴素的求lca的方法是：
不妨设x为深度更深的点，不断让x往上爬，直到dep[x]==dep[y],如果x==y就返回，如果不等于就让x和y 一起往上跳，直到x==y再返回，思路简单，复杂度高。所以就有了倍增法求lca：本质上是dp，类似st表，fa[i][j]表示i号节点，往上走2^j所到的节点，当dep[i]-2^j>=1时fa[i][j]有效（设根节点深度为1）
例：

 1 | 2 | 3 | 4 \ 5

fa[5][0]=4(从5向上走2^0),fa[5][1]=fa[fa[5][0]][0]=3
由此得出：

代码：

void dfs(int x, int p)//p:父节点 { dep[x] = dep[p] + 1; fa[x][0] = p; for (int i = 1; i <= 20; i++) { fa[x][i] = fa[fa[x][i - 1]][i - 1]; } for (const auto& y : g[x]) { if (y == p)continue; dfs(y, x); } } 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[fa[x][i]] >= dep[y])x = fa[x][i]; } if (x == y)return x;//二者相同，直接返回 //与y同层之后，二者同时向上跳,但要保持x！=y for (int i = 20; i >= 0; i--) { if (fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i]; } return fa[x][0];// x的父节点就是LCA（此时x和y的父节点相同） }

例题：

蓝桥杯官网——最近公共祖先lca查询(模板题)

问题描述

给定一棵有 N 个节点的树，每个节点有一个唯一的编号，从 1 到 N。树的根节点是 1 号节点。接下来，你会得到 Q 个查询。对于每个查询，你将得到两个节点的编号，你的任务是找到这两个节点的最低公共祖先。

输入格式

第一行包含一个整数 N，表示树的节点数。

接下来的 N−1 行，每行包含两个整数 U 和 V，表示节点 U 和节点 V 之间有一条边。

下一行包含一个整数 Q，表示查询的数量。

接下来的 Q 行，每行包含两个整数 A 和 B，表示你需要找到节点 A 和节点 B 的最低公共祖先。

输出格式

对于每个查询，输出一行，该行包含一个整数，表示两个节点的最近公共祖先。

样例输入

5 1 2 1 3 2 4 2 5 3 4 5 3 4 3 5

样例输出

2 1 1

样例说明

对于第一个查询，4 和 5 的最低公共祖先是 2。

对于第二个查询，3 和 4 的最低公共祖先是 1。

对于第三个查询，3 和 5 的最低公共祖先是 1。

测评数据规模

2≤N≤10^5，1≤Q≤10^4，1≤U,V,A,B≤N，题目保证输入的边形成一棵树。

代码详解：

#include <iostream> #include<vector> using namespace std; const int N=1e5+9; int fa[N][24],dep[N]; vector<int>g[N]; void dfs(int x,int p) { dep[x]=dep[p]+1; fa[x][0]=p; for(int i=1;i<=20;i++) { fa[x][i]=fa[fa[x][i-1]][i-1]; } for(const auto&y:g[x]) { if(y==p) continue; dfs(y,x); } } int lca(int x,int y) { //先判断深度要深的向上跳，默认x if(dep[x]<dep[y]) swap(x,y); //贪心，先使得x，y同层 for(int i=20;i>=0;i--) { if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; } //到达同一层，又要分两种情况：1，xy此时相遇 if(x==y) return x; //2,xy不相遇:二者同时向上跳,但要保持x！=y for(int i=20;i>=0;i--) { if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; } return fa[x][0];//此时返回二者任意节点的父节点，就是lca！ } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n;cin>>n; for(int i=1;i<n;i++) { int u,v;cin>>u>>v; g[u].push_back(v),g[v].push_back(u); } dfs(1,0); int q;cin>>q; while(q--) { int x,y;cin>>x>>y; cout<<lca(x,y)<<'\n'; } return 0; }

方法二：tarjan求lca

Tarjan 算法求 LCA（基于并查集的离线算法）的核心优势在于高效处理多组查询，尤其适合需要一次性解决大量 LCA 查询的场景。以下是其具体优势的详细解释：

1. 时间复杂度极低，适合大规模查询

（1）Tarjan 算法是离线算法（需先收集所有查询，再一次性处理），其时间复杂度为 O(n + q)，其中 n 是树的节点数，q 是查询次数。

（2）对比倍增算法（在线算法，单次查询 O (logn)）：当查询次数 q 很大（如 q = 1e5 甚至 q = 1e6）时，Tarjan 算法的总效率更高（n + q 远小于 q * logn）。

2. 利用并查集实现 “路径压缩”，合并与查询高效

（1）算法核心依赖并查集（Union-Find）的数据结构，通过 root(x) 快速查找节点所在集合的根，并用路径压缩优化查询效率。

（2）在遍历树的过程中，通过 “合并子树到父节点” 的操作，天然维护了 “节点与其祖先的连通性”，避免了重复计算。

3. 一次遍历处理所有查询，减少树的访问次数

（1）算法通过深度优先搜索（DFS） 遍历树一次，在回溯时完成并查集的合并，并同步处理所有与当前节点相关的查询。

（2）相比在线算法（如倍增）需要对每个查询单独遍历树的部分路径，Tarjan 算法只需遍历树一次，大幅减少了对树结构的重复访问。

4. 适用于静态树的批量查询场景

若问题中所有查询在处理前已知（离线场景），Tarjan 算法是最优选择之一。例如：
- 批量查询树上多对节点的 LCA；
- 基于 LCA 计算多对节点的路径长度、距离等衍生问题。
典型应用：家谱树中批量查询亲属关系、网络拓扑中批量计算节点间最短路径等。

5. 实现逻辑直观，依托 DFS 与并查集的天然契合

（1）算法利用 DFS 的回溯特性：当遍历完一个节点的所有子树后，该节点与其子树的所有节点已被合并到同一集合，且集合的根为该节点（或更高祖先）。

（2）此时若查询中存在与该节点相关的配对（且另一节点已被访问），则两节点的 LCA 就是 “已访问节点所在集合的根”，逻辑清晰且易于理解。

总结

Tarjan 算法求 LCA 的核心优势是离线处理下的高效性，尤其在查询数量庞大时，其 O (n + q) 的时间复杂度远优于在线算法。但需注意其局限性：必须提前知晓所有查询（无法处理动态新增的查询），且依赖并查集和 DFS 的配合。

对比而言：

（1）若需要动态查询（查询逐步到来），优先选倍增算法；

（2）若查询一次性给出且数量大，Tarjan 算法是更优解。

代码：

int root(int x) { return pre[x] = (pre[x] == x ? x : root(pre[x])); } vector<int>vec[N]; // 记录需要做lca的点对，就是1到m的查询点 bitset<N>vis; // 标记节点是否被访问过 map<int, int>lca[N]; // 存储点对的lca结果 /*vis 是一个 bitset，用于标记节点是否已完成所有子树的遍历（即「回溯完成」）。 只有当节点的所有子节点都处理完毕后，才会标记为 true。*/ void tarjan(int x, int father)// Tarjan算法求LCA { fa[x] = father; //这一步是在遍历x的所有子节点，及子节点的子节点 for (const auto& y : g[x]) { if (y == fa[x])continue; tarjan(y, x); pre[root(y)] = root(x); /*当子节点 y 的所有子树都处理完毕后，执行 pre[root(y)] = root(x)： 将 y 所在集合的根节点（root(y)）合并到 x 所在集合的根节点（root(x)）中。 这一步的作用是：标记 y 及其子树已处理完毕，并将它们归入 x 的集合，为后续计算 LCA 做准备。*/ //y是x的子节点，y的根有可能就是x，所以可将y集合并入x集合中 } vis[x] = true;//说明x已经查询过了 for (const auto& y : vec[x])//处理与x有关的查询，比如我要查询3,5是否有公共祖先，y就是5，x就是3 { if (vis[y])lca[x][y] = lca[y][x] = root(y);//若y也被查询过，说明在之前遍历x及其子树的过程中 //y出现过了 //则y与x必然联通，二者必然有lca！ /*此时 root(y) 之所以是 LCA，原因如下： y 已处理完毕，意味着 y 的所有祖先（包括 LCA）都已完成合并， root(y) 指向 y 所在分支中最深的已合并祖先。 x 正在处理中（尚未合并到父节点），而 y 已处理，说明 x 和 y 的公共祖先中， 最深的那个就是 root(y)（因为 y 已合并到该祖先的集合中，而 x 还未继续向上合并）。*/ } }

例题：

就是上面那道：

#include<utility> #include<iostream> #include<vector> #include<queue> #include<algorithm> #include<bitset> using namespace std; const int N=2e5+9; int pre[N],ans[N]; vector<int>g[N]; //需要一个结构体，来存储每个查询点以及对应的另一个查询点和编号 //因为最终要输出一个答案数组，所以要有编号 struct Q { int x,id; }; vector<Q>q[N];//存储查询点对和对应的编号 int root(int x) { return pre[x]=(pre[x]==x?x:root(pre[x])); } bitset<N>vis; void tarjan(int x,int fa) { vis[x]=true; for(const auto&y:g[x]) { if(y==fa) continue; tarjan(y,x); pre[y]=x;//相当于pre[root(y)]=root(x); } for(const auto& t:q[x]) { int y=t.x,id=t.id; if(vis[y]) ans[id]=root(y); } } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n;cin>>n; for(int i=1;i<n;i++) { int u,v;cin>>u>>v; g[u].push_back(v),g[v].push_back(u); } //不要忘了初始根！！！ for(int i=1;i<=n;i++) pre[i]=i; int m;cin>>m; for(int i=1;i<=m;i++) { int x,y;cin>>x>>y; q[x].push_back({y,i}); q[y].push_back({x,i}); } tarjan(1,0); for(int i=1;i<=m;i++) cout<<ans[i]<<'\n'; }

okkkkkkk了，如果觉得不错，就麻烦点赞+关注+收藏吧！

c++基础树上问题——求lca（最近公共祖先）的几种方法，算法必看哟！

Ne0inhk

一，lca简介

核心定义

应用场景

关键特性

二，求lca的方法

方法一：朴素求lca（倍增求lca）

代码：

例题：