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）
例：

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 的最低公共祖先。

输出格式

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

样例输入

样例输出

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了，如果觉得不错，就麻烦点赞+关注+收藏吧！