没有合适的资源？快使用搜索试试~ 我知道了~

文库首页后端C++LCA多种算法讲解（含版题代码）

LCA多种算法讲解（含版题代码）

需积分: 0 0 下载量 113 浏览量 2023-05-28 16:01:59 上传评论收藏 768KB PDF 举报

温馨提示

试读

20页

LCA讲解，有图片与版题（含代码）帮助理解

资源推荐

资源详情

资源评论

第 2 章区间信息维护与查询┃

2.2 最近公共祖先 LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖

先。祖先指从当前节点到树根路径上的所有节点。

u 和 v 的公共祖先指一个节点既是 u 的祖先，又是 v 的祖先。u 和 v 的最近公共祖先指距离

u 和 v 最近的公共祖先。若 v 是 u 的祖先，则 u 和 v 的最近公共祖先是 v。

可以使用 LCA 求解树上任意两点之间的距离。求 u 和 v 之间的距离时，若 u 和 v 的最近公

共祖先为 lca，则 u 和 v 之间的距离为 u 到树根的距离加上 v 到树根的距离减去 2 倍的 lca 到树

根的距离：dist[u]+dist[v]2×dist[lca]。

u的祖先

u、v的最近

公共祖先

u、v的最近

公共祖先

┃算法训练营：海量图解+竞赛刷题（进阶篇）

lca

…

u、v的最近

公共祖先

root

u、v之间

的距离

lca

…

u、v的最近

公共祖先

root

dist[u]

dist[v]

dist[lca]

求解 LCA 的方法有很多，包括暴力搜索法、树上倍增法、在线 RMQ 算法、离线 Tarjan 算

法和树链剖分。

在线算法：以序列化方式一个一个地处理输入，也就是说，在开始时并不需要知道所有输

入，在解决一个问题后立即输出结果。

离线算法：在开始时已知问题的所有输入数据，可以一次性回答所有问题。

 原理 1 暴力搜索法

暴力搜索法有两种：向上标记法和同步前进法。

1．向上标记法

从 u 向上一直到根节点，标记所有经过的节点；若 v 已被标记，则 v 节点为 LCA(u, v)；否

则 v 也向上走，第 1 次遇到已标记的节点时，该节点为 LCA(u, v)。

2．同步前进法

将 u

、

v 中较深的节点向上走到和深度较浅的节点同一深度，然后两个点一起向上走，直到

走到同一个节点，该节点就是 u

、

v 的最近公共祖先，记作 LCA(u,v)。若较深的节点 u 到达 v

的同一深度时，那个节点正好是 v，则 v 节点为 LCA(u, v)。

u、v的最近

公共祖先

u、v的最近

公共祖先

第 2 章区间信息维护与查询┃

u、v的最近

公共祖先

同一深度

u、v的最近

公共祖先

同一深度

3．算法分析

以暴力搜索法求解 LCA，两种方法的时间复杂度在最坏情况下均为 O(n)。

 原理 2 树上倍增法

树上倍增法不仅可以解决 LCA 问题，还可以解决很多其他问题，掌握树上倍增法是很有必

要的。

F[i, j]表示 i 的 2

辈祖先，即 i 节点向根节点走 2

步到达的节点。

u 节点向上走 2

步，则为 u 的父节点 x，F[u,0]=x；向上走 2

步，到达 y，F[u,1]=y；向上走

步，到达 z，F[u,2]=z；向上走 2

步，节点不存在，令 F[u,3]=0。

F[i, j]表示 i 的 2

辈祖先，即 i 节点向根节点走 2

步到达的节点。可以分两个步骤：i 节点先

向根节点走 2

j1

步得到 F[i, j1]；再从 F[i, j1]节点出发向根节点走 2

j1

步，得到 F[F[i, j1], j1]，

该节点为 F[i, j]。

剩余19页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

GG_Bond...

粉丝: 527
资源: 2

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

LCA多种算法讲解（含版题代码）

LCA详解，内附算法、代码

Pascal LCA 倍增法详解及代码

Tarjan 的 LCA 算法

LCA算法的讲解（非常详细）

【智能优化算法】联盟竞赛优化算法LCA附matlab代码.zip

slca算法的实现

LCA的tarjan算法

lca_one_layer.zip_LCA_LCA算法_图像分析_图像基元_基元 matlab

lca51早期版本

Tarjan算法 讲解

xml关键字查询求SLCA代码

常用算法代码

ACM算法模板和pku代码

Tarjan应用LCA

XML关键字搜索中一个高效的寻找XLCA的算法

RMQ与LCA ACM必备

RMQ&LCA;问题

RMQ与LCA问题

高效多目标优化 (TSEMO) 算法.zip

最近公共祖先（LCA）板子代码

第十五届蓝桥杯大赛软件赛省赛C++B组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

编译器（gcc、g++）

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

Qt5.9 C++开发指南.pdf 及示例源码

Qt （高仿Visio）流程图组件开发，源码分享

mingw-w64-install.exe

Qt、QCustomPlot、实时波形绘制、实时曲线绘制

最新资源

Tarjan算法讲解