沿父节点指针走一步很便宜;但如果每次查询都要走上千步,就会重复许多工作。如果事先存下顶点向上走 1、2、4、8 以及更多二次幂步后的位置,就可以根据步数的二进制位拼出较长的向上路径。
这就是二进制跳跃,也称祖先倍增。倍增的思想与快速幂相似,不过这里复合的是父节点映射,而不是数字。我们先证明表中每一项的含义,再用表寻找最近公共祖先。后一个算法需要自己的不变量:能够快速跳跃,并不意味着我们已经知道哪些跳跃是安全的。
预处理后,树和所选根保持不变。该方法支持静态祖先和距离查询;它不能替代重链剖分来维护路径上一般的动态变化数值。
有根树中,深度与表的约定是两回事
输入是一棵非空无向树,顶点为 ,选定根 。树连通且无环,所以任意两点之间恰有一条简单路径。深度 是从根到 的路径上的边数。非根顶点的父节点是该路径上紧邻它的前一个顶点。
定义 13.2.1
(真实祖先与在根处截停的父节点映射)
对整数 , 的第 级祖先是向根方向恰好走 次父节点所到达的顶点。当且仅当 时,它存在。第零级祖先是 自身;根的上方没有真实祖先。
仅为了构造表,定义全定义映射 :非根顶点映射到真实父节点,并令 。存储
这里的指数表示函数复合的次数。如果表中的跳跃走得过远,映射就停在根处。这样的填充使每次查表都有定义,但不会改变真实第 级祖先的存在条件。
定义 13.2.2
(最近公共祖先)
一个顶点的真实祖先恰好是它的根路径上的顶点,包括它自己。两个顶点的根路径的交集是一段共同的初始路径,其中深度最大的顶点就是唯一的最近公共祖先,简称 LCA。“最近”指深度最大,而不是顶点标签最小。
复合同一个父节点操作的不同幂
定理 13.2.3
(以二进制合成求第 k 个祖先)
对每个顶点 与每个整数 ,把 写成 ,其中 。从 出发,对每个满足 的 ,把当前顶点换成它在第 行的值 ,结果就是 的第 个祖先;而且每个这样的 都是已存储的行,行数 是 的二进制位数,至少为 。
证明
(倍增与二进制位)
基本行应用一次 。如果第 行应用 次 ,那么连续应用该行两次就相当于应用 次,从而由归纳法证明下一行的含义。
将有效查询写作 ,其中 。对每个为一的位,都把当前顶点替换为其第 行祖先。由于这些操作是同一映射的不同幂,复合后恰好应用 共 次。所选步数的每个部分和都不超过 ,所以过程中不会用到根上方人为填充的部分。
对于有 个顶点的树,深度至多为 。因此 行(编号从 0 到 )足以表示每个有效距离。单顶点情况保留一行基本行。根据查询的二进制位访问表之前,应先检查它是否超过深度。
证明透视
为什么表中填充的部分从不被碰到
证明只需要 提供的一件事:所选各个二的幂的每个部分和都不超过 ,所以每个中间顶点都是真实祖先,填充规则 从未被使用。跳跃的次序无关紧要,因为同一个映射的各次幂互相可交换。行数则是另一个纯算术的事实: 限制了 的最高设定位。
反例模式
根处填充不意味着存在无限多个祖先
对深度为 2 的顶点,查询它的第三级祖先没有答案。如果表中根指向自身,而查询时没有检查深度,仍然会返回根。这个结果描述的是填充后的映射,并非三次真实的父节点移动。
代码在 时返回 None,并拒绝负数 。特别地,根的第零级祖先是根本身,但第一级祖先不存在。对于极大的无效 ,必须先用深度界拒绝,不能让它请求不存在的表行。
一棵分支树上的跳跃表
例题 13.2.4
(用一步与四步跳跃拼出五步上行)
取八个顶点,根为 0,边为 、、、、、、。两条分支在顶点 2 分开。由于 有三位二进制数字,三行表就足够。
| 顶点 | 深度 | :一步 | :两步 | :四步 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 2 | 2 | 1 | 0 | 0 |
| 3 | 3 | 2 | 1 | 0 |
| 4 | 4 | 3 | 2 | 0 |
| 5 | 5 | 4 | 3 | 1 |
| 6 | 3 | 2 | 1 | 0 |
| 7 | 4 | 6 | 2 | 0 |
从顶点 5 向上走五步,利用 :先跳到 ,再跳到 。也可以先走四步到达 1,再走一步到达 0。两种顺序都复合了相同的五次父节点操作。查询第六级祖先会返回 None,尽管复合填充后的表仍会停在 0。
例题 13.2.5
(路径图与全深度祖先)
设树为以 为根的路径 ,故 , 行分别存放 步的跳跃。 的第七个祖先用 :,接着 ,再 ,正是 。全深度的祖先 :,然后 ,即根。请求 时返回 None,虽然填充后的合成也会落在 。
比较两条向上路径之前先对齐深度
要找 ,首先将较深的端点向上提升两个深度之差。LCA 不会改变:被移除的顶点都低于较浅端点的深度,不可能是公共祖先。此时两个当前顶点深度相同。如果它们重合,该顶点就是答案,包括原来一个端点是另一个端点祖先的情况。
否则,当前顶点不同,并且都严格位于真正的 LCA 之下。考虑两者同时跳跃相同步数 。如果提议到达的祖先不同,两次跳跃都会严格停在 之下,可以安全执行;如果提议的祖先相同,跳跃就会到达或越过 ,执行它可能跳过答案。
定理 13.2.6
(LCA 扫描的正确性)
把 中较深的一个向上提升深度差。若两个顶点相同,该顶点就是 。否则依 扫描,每当两者在第 行的祖先不同,就把两个顶点都换成它们。扫描结束时得到两个不同的顶点,其共同父顶点就是 。
证明
(由大到小的不等跳跃)
深度相同且互不相同的两个顶点到其 LCA 的距离相同,记为正数 。它们的向上路径在到达 之前互不相交,之后重合。因此 当且仅当 。即使跳跃会越过根,在根处截停的查表方式也会保持相等。
当提议的祖先不同时,用它们替换两个端点,相当于从 中减去 ,并保持同一个 LCA;否则不移动端点。从 到 0 递减扫描各层。初始时 。若处理第 层之前有 ,则要么 而不跳,要么跳跃减去 ,留下 。
由归纳法,处理完第 0 层后,。当前两个顶点是 的不同子节点,所以它们的共同父节点恰好就是答案。算法运行时无需知道 ;两个提议表项不相等,就足以证明每次移动安全。
证明透视
为什么用不相等作判断
扫描只用到未知 LCA 的一个事实:两个位于 下方同样距离 的顶点,它们在第 行的祖先不同,当且仅当 。所以“不同”保证这次跳跃仍严格停在 之下,而“相同”只表示跳跃会到达或越过 ,并不说明 有多远。不变量 使扫描成为对 的二分搜索:每一层要么因 而保持 不变,要么减去 并使 。若从第 层向上扫描就会失败,因为较早取的小跳跃可能留下一个需要更大跳跃的距离,而更大的跳跃已经过去了。
反例模式
祖先相等时跳跃可能跳过所求祖先
考虑以 0 为根、边为 、、 的树。2 和 3 的 LCA 是 1,它们的两步表祖先却都是 0。如果仅因这两个表项相等就把端点都移到那里,就会越过顶点 1,丢失答案。
正确的循环在提议祖先不相等时移动,始终停在 LCA 下方。提议相等意味着应尝试更短的跳跃。深度对齐之后的相等判断则不同:如果当前顶点本身已经重合,就已经到达答案,应立即返回。
常见错误
(由小到大扫描层次)
层次必须由 扫到 。取两个位于其 LCA 下方距离 的顶点。若由小到大扫描,第 层的祖先不同,两者上移一步,剩下 ;第 层的提议已经相同,所以不动;扫描结束时仍在 LCA 下方两条边,返回的是真正 LCA 的一个子顶点,答案错误。由大到小则先试 步跳跃,拒绝它,再取 步跳跃,拒绝 步跳跃,停在距离 处,其父顶点就是 LCA。
推导无权距离
定理 13.2.7
(由深度与 LCA 得出距离)
对树中的顶点 ,设其最近公共祖先为 ,则唯一的 – 路径的边数为
证明
(先向上再向下)
路径沿 条边从 向上到 ,再沿 条边向下到 。两段没有共同的边,因为在 之下它们位于不同的根路径上;若 或 ,其中一段为空。把两个数目相加就得到公式。
常见错误
(深度不是加权距离)
这个公式计算的是边数。如果边有其他长度或权重,普通深度并不是带权距离,不能在不修改所存数据和证明的情况下直接代入。
例题 13.2.8
(先对齐,再停在分支点下方)
在八顶点树中,顶点 5 的深度为 5,顶点 7 的深度为 4。将 5 向上提升一步到 4,于是在深度 4 比较顶点 4 和 7。四步提议都得到 0;两步提议都得到 2。两次都不移动。
一步提议分别是 3 和 6,它们不同。移动到这两个顶点,然后返回它们共同的父节点 2。因此 ,距离为 。实际路径为 ,包含五条边。
对于端点 3 和 5,对齐深度时就把 5 提升到了 3,所以在同步跳跃循环之前返回 LCA。若两个端点相同,LCA 就是该顶点,距离为零。
带树输入约定的可执行实现
构造函数接受正整数 、由整数端点对组成的无向边列表,以及整数根标签。它验证端点、恰有 条边实例以及连通性。后两个条件保证输入是一棵树,即使列表中试图包含自环或重复边也是如此:连通图已经需要 条生成树边,因此没有多余的边实例可供自环、平行副本或环使用。
广度优先遍历不使用递归,记录父节点和深度。队列在发现顶点时立即标记。查询标签必须位于 ;访问表之前会拒绝无效或负数标签。构造函数读取边列表,但不修改它。
from collections import deque
class AncestorTable:
def __init__(self, n, edges, root=0):
if n <= 0 or not 0 <= root < n:
raise ValueError("a nonempty tree and a valid root are required")
graph = [[] for _ in range(n)]
edge_count = 0
for u, v in edges:
if not (0 <= u < n and 0 <= v < n):
raise ValueError("edge endpoint outside the vertex range")
graph[u].append(v)
graph[v].append(u)
edge_count += 1
if edge_count != n - 1:
raise ValueError("a tree must have exactly n - 1 edges")
parent = [-1] * n
depth = [0] * n
parent[root] = root
pending = deque([root])
reached = 1
while pending:
vertex = pending.popleft()
for neighbor in graph[vertex]:
if parent[neighbor] == -1:
parent[neighbor] = vertex
depth[neighbor] = depth[vertex] + 1
reached += 1
pending.append(neighbor)
if reached != n:
raise ValueError("the tree must be connected")
self.n = n
self.depth = depth
self.up = [parent]
levels = max(1, (n - 1).bit_length())
for _ in range(1, levels):
previous = self.up[-1]
self.up.append([previous[previous[v]] for v in range(n)])
def _vertex(self, vertex):
if not 0 <= vertex < self.n:
raise IndexError("vertex outside the tree")
def ancestor(self, vertex, k):
self._vertex(vertex)
if k < 0:
raise ValueError("the ancestor distance must be nonnegative")
if k > self.depth[vertex]:
return None
level = 0
while k:
if k & 1:
vertex = self.up[level][vertex]
k >>= 1
level += 1
return vertex
def lca(self, u, v):
self._vertex(u)
self._vertex(v)
if self.depth[u] < self.depth[v]:
u, v = v, u
u = self.ancestor(u, self.depth[u] - self.depth[v])
if u == v:
return u
for level in range(len(self.up) - 1, -1, -1):
if self.up[level][u] != self.up[level][v]:
u = self.up[level][u]
v = self.up[level][v]
return self.up[0][u]
def distance(self, u, v):
common = self.lca(u, v)
return self.depth[u] + self.depth[v] - 2 * self.depth[common]
代码假定标签、数量和 值满足约定,均为整数。有效的深度对齐操作不会返回 None,因为所需距离至多为较深端点的深度。只有一个顶点时,表为 [[0]],祖先距离为零时返回 0,任何正距离都返回 None,而 lca(0,0) 返回 0。
命题 13.2.9
(祖先表的开销)
对有 个顶点的树,预处理需时 、占用相同量级的空间;在索引、位运算与整数算术都是常数时间的假设下,每次祖先、LCA 或距离查询需时 。
证明
(计算行数与循环次数)
对有效输入,建立图及其有根父节点数据需要 时间。表有 个单元,填表需要 时间。因此预处理时间和存储均为 ;在标准索引、位运算和整数运算假设下,每次祖先、LCA 或距离查询的最坏时间为 。这里加一是为了包含单顶点情况。这些并不是任意大整数的位复杂度界。
改变所选根会改变祖先关系,也可能改变 LCA;但不会改变唯一的无向路径及其边数。构造后改变树的边会使预处理失效;动态拓扑需要另外的数据结构,或者重新构建。
练习与完整解答
快速检查
(1. 在八顶点例子中,求顶点 5 的第三级、第五级和第六级祖先。解释为什么对最后一个查询,只使用填充后的查表结果不够。)
解答 · 1. 区分真实步数与根处填充
第三级祖先沿 到达 2;第五级祖先是 0。第六级祖先不存在,因为顶点 5 的深度为 5,所以函数返回 None。将填充后的映射复合六次会停在 0,但这不是真实的第六级祖先。深度检查保证了查询的既定含义。
快速检查
(2. 从两步表项推导四步表项 。虽然没有表行直接存储三步,为什么同一张表仍能回答三步查询?)
解答 · 2. 复合已存储的二次幂得到其他距离
且 ,所以 。三步使用 :一步到达 4,再走两步到达 2。表行存储二次幂,二进制复合则提供这些幂的每个有效和。
快速检查
(3. 求例子中的 LCA(5,7) 及两者之间的边距离。对齐深度后,实际执行了哪次同步跳跃?)
解答 · 3. 最后一步取父节点之前始终停在公共祖先下方
先将 5 提升到 4。四步和两步提议都相等,因此不执行。一步提议是 3 和 6,于是两个顶点分别移到那里;它们的父节点 2 就是 LCA。边距离为 ,与路径 一致。
快速检查
(4. 在以 0 为根、1 连接叶子 2 和 3 的树中,为什么从 2 和 3 执行相等的两步提议是错误的?什么时候相等反而可以立即返回?)
解答 · 4. 提议跳跃相等与当前顶点相等不同
两步提议都到达 0,它高于真正的 LCA 1。执行跳跃会丢失最近公共祖先,因此同步循环只执行不相等的提议。深度对齐后,如果当前端点本身相等,该共同顶点已经是 LCA,应立即返回。这是含义不同的两种相等判断。
快速检查
(5. 在路径 0-1-2 上,比较以 0 为根和以 2 为根时的 LCA(0,2)。边距离会改变吗?)
解答 · 5. 祖先关系依赖于根,距离不依赖于根
以 0 为根时 LCA 是 0;以 2 为根时 LCA 是 2。两者分别对应相应有根路径的共同初始部分。唯一的无向路径仍有两条边,任一根下使用深度公式都得到 2。要使用新根下的祖先关系,必须重新预处理。
快速检查
(6. 某输入 n=4,边为 (0,1)、(1,2)、(2,0)。既然它有 n−1 条边,构造函数为什么仍必须拒绝?对无向边列表输入,为什么边数与连通性合在一起就足够?)
解答 · 6. 仅靠边数不能证明输入是一棵树
这些边在三个顶点上构成三角形,并使顶点 3 孤立,因此连通性检查失败。每个连通无向图都有一棵包含 条边实例的生成树。如果整个输入也恰好有这么多边,那么所有输入边都必须属于生成树,没有额外边可以组成环、自环或平行副本。接受的树输入必须同时满足这两个条件。