算法与数据结构 · 第 27 课

二进制提升与 LCA:怎样用 O(log n) 查询一条树路径上的最大边?

2026 年 11 月 15 日|第 4 周 · 第 6 天|讲授约 17 分钟(自测另计)

昨天计算 MST 的唯一性、次小生成树时,对每条非树边 (u,v) 都沿树路径逐边扫描,最坏需要 O(n) 时间。今天不改变 MST 证明,而是建立一个更快的树路径查询器:预存向上走 1、2、4、8……条边的结果,用二进制拆分任意向上路径。

一、学习目标与模型(约 2 分钟)

学完应能:(1) 理解最低公共祖先 LCA;(2) 建立 up[k][v] 和 mx[k][v] 两张倍增表;(3) 手工执行“对齐深度 → 同步上跳 → 汇总两条末端边”;(4) 证明路径没有遗漏或重复;(5) 将每条非树边的 MST 换边代价查询从 O(n) 降为 O(log n)。

输入是一棵有 n≥2 个顶点的无向加权树 T,任选根 r。边权可以为负,也可以相等。深度 depth[v] 是从根到 v 的边数,不是加权距离。对于不同顶点 u、v,定义

[ M(u,v)=\max_{e\in P_T(u,v)}w(e). ]

LCA(u,v) 是同时为 u、v 祖先且深度最大的节点。树上唯一路径先从 u 向上到 LCA,再向下到 v;因此可以分别向上处理两段。

二、示意图与动机(约 2 分钟)

flowchart TD
    A["A · depth 0"] ---|"1"| B["B · depth 1"]
    B ---|"4"| C["C · depth 2"]
    B ---|"-2"| D["D · depth 2"]
    D ---|"3"| E["E · depth 3"]
    D ---|"5"| F["F · depth 3"]
    E ---|"2"| G["G · depth 4"]

以 A 为根。查询 C 到 G 的路径是 C–B–D–E–G,路径边权为 4、−2、3、2,最大值为 4。查询 A 到 E 时,路径 A–B–D–E 的最大边权为 3。

如果用 DFS 每次重找路径,单次最坏 O(n);若有 m 条非树边,可能需要 O(mn)。然而树结构不变,我们完全可以提前把每个顶点向上走固定长度的结果算好,重复利用。

三、两张倍增表:一段长度为 2^k 的摘要(约 3 分钟)

令 K=⌊log₂n⌋。定义:

  • up[k][v]:v 向上走恰好 2^k 条边到达的祖先;若不存在记为 NIL。
  • mx[k][v]:这 2^k 条边上的最大权重;若不足 2^k 条边,记为 −∞,对应祖先为 NIL。

初始 up[0][v]=parent[v],有父亲时 mx[0][v]=w(v,parent[v])。根节点的 up[0] 为 NIL,mx[0] 为 −∞。对于 k≥1,把 2^k 条边拆成连续的两段 2^(k−1):

[ \begin{aligned} a&=up[k-1][v],
up[k][v]&=up[k-1][a],
mx[k][v]&=\max(mx[k-1][v],mx[k-1][a]). \end{aligned} ]

只在两段均存在时应用递推;否则 up[k][v]=NIL、mx[k][v]=−∞。这个约定避免把不存在的祖先误当作真实顶点。注意汇总操作是 max,不是权重求和;换成 sum、min 等满足结合律的聚合量时也可用相同思想。

PREPROCESS(T, root):
    DFS(root) 建立 parent、depth、parentEdgeWeight
    K = floor(log2(n))
    对每个 v:
        up[0][v] = parent[v]
        mx[0][v] = parentEdgeWeight[v] 若 parent[v] 存在,否则 -INF
    for k = 1..K:
        for v in V:
            a = up[k-1][v]
            if a != NIL and up[k-1][a] != NIL:
                up[k][v] = up[k-1][a]
                mx[k][v] = max(mx[k-1][v], mx[k-1][a])
            else:
                up[k][v] = NIL
                mx[k][v] = -INF

四、查询算法:先对齐,再同步上跳(约 3 分钟)

查询时维护 ans,表示已经走过的边上的最大权重。先把更深的顶点抬到与另一顶点同深度;如果已经重合,它就是 LCA。否则从最大的 k 向下检查:若两者的 2^k 祖先存在而且不同,则两者都可以向上跳 2^k 边,同时纳入这两段的最大值。结束时,它们的父亲相同,这个父亲就是 LCA;最后必须把各自到父亲的两条边也纳入。

PATH_MAX_AND_LCA(u, v):
    assert u != v
    ans = -INF
    if depth[u] < depth[v]: swap(u,v)

    diff = depth[u] - depth[v]
    for k = K downto 0:
        if bit_k(diff) == 1:
            ans = max(ans, mx[k][u])
            u = up[k][u]

    if u == v: return (u, ans)

    for k = K downto 0:
        if up[k][u] != NIL and up[k][u] != up[k][v]:
            ans = max(ans, mx[k][u], mx[k][v])
            u = up[k][u]
            v = up[k][v]

    ans = max(ans, mx[0][u], mx[0][v])
    return (up[0][u], ans)

数值 Trace:查询 C、G。 两者深度分别为 2、4。先把 G 上跳 2 条边到 D,经过 G–E(2) 和 E–D(3),所以 ans=3。现在 C 与 D 都在深度 2,它们的父亲同为 B,因此同步上跳阶段不再跳;最后纳入 C–B(4)、D–B(−2),得到 LCA(C,G)=B,路径最大值 M(C,G)=4。

再查询 A、E:把 E 上跳两条边到 B(最大 3),再上跳一条边到 A(边权 1),因此 M(A,E)=3。深度差的二进制分解负责“一边上升”;同步倍增负责“找到分叉处”。

五、正确性证明:倍增摘要与路径分解(约 3 分钟)

预处理不变量。 对每个存在的 up[k][v],它恰好是 v 上方 2^k 条边的祖先;mx[k][v] 恰好是这一整段的最大边权。k=0 由父节点定义成立;k>0 将连续路径等分为两个长度 2^(k−1) 的段,祖先可复合,最大值可取两段最大值,归纳成立。

查询不变量。 在任意一次上跳之后,ans 等于已经从原始 u、v 两端走过的边的最大权重;尚未走过的部分仍连接当前两个位置。每次跳跃的 2^k 条边由 mx 精确汇总,故不遗漏也不添加无关边。

对齐深度后,若 u=v,已走过的就是整条原路径。否则,从高位到低位,只在两者的 2^k 祖先不同且存在时同步上跳,因此不会越过真正的 LCA;扫描结束时二者仍不同、但父亲相同。将最后两条父边计入后,原路径被分成互不重叠的若干上跳段,ans=M(u_original,v_original),公共父亲即真正 LCA。

这里的证明还说明为什么不能把两端一起跳到相同祖先后才停止:那样可能跨过 LCA,遗漏临近分叉处的边。

六、重新计算昨天的 MST 问题(约 2 分钟)

假设上图的六条树边构成已知 MST,树权重为

[ W(T)=1+4-2+3+5+2=13. ]

原图还有四条非树边,分别为 A–E(4)、C–G(6)、C–F(8)、E–F(7)。对每条边 e=(u,v),用上述查询得到路径最大值 M(e),再计算加入 e、删去原路径最大边后的增量 (\Delta(e)=w(e)-M(e))。

非树边 e M(e) Δ(e)
A–E (4) 3 1
C–G (6) 4 2
C–F (8) 5 3
E–F (7) 5 2

所有增量都大于零,所以这棵 MST 唯一。最小增量为 1,严格次小生成树权重为 14。这一步调用的是昨天证明过的 MST 换边定理;今天的倍增只负责快速、准确地计算 M(e),没有改变最优性论证。

七、复杂度与边界反例(约 1 分钟)

树上 DFS 建根关系 O(n);共有 O(log n) 层,每层处理 n 个顶点,预处理时间和空间都是 O(n log n)。一次查询最多遍历两轮长度 O(log n) 的位循环,因此 O(log n) 时间、O(1) 查询额外空间(不计预处理表)。把全部非树边查询完需 O(m log n) 时间;连同 Kruskal 构建 MST,整体可写为 (O(m\log(m+1)+(n+m)\log n)) 时间,存图及倍增表 O(m+n log n) 空间。

边界 1:负边。 不能把 ans 或表中“不存在的段”初始化成 0;当查询路径所有边权都为负数,0 会产生不存在的最大值,应使用 −∞。边界 2:同一个顶点。 P_T(u,u) 没有边,最大边权没有通常意义;本课规定只查询 u≠v。边界 3:动态修改。 该表只针对静态树有效,若修改树边或其权重,应重新预处理或换用动态树结构。边界 4:非连通图。 LCA 与路径最大值只对同一棵树内的顶点有定义;森林必须先判断是否同分量。边界 5:不是 MST。 任意生成树也可做倍增查询,但 (\Delta(e)) 可能为负,不能直接套用“已知 MST 的唯一性”结论。

八、小结与下一课(约 1 分钟)

[ \boxed{\text{预处理 }2^k\text{ 级祖先和路径摘要} \ \Longrightarrow\ \text{二进制上跳} \ \Longrightarrow\ O(\log n)\text{ 的 LCA 与路径最大边}} ]

今天的关键不是记住表的下标,而是理解把长路径拆成若干不重叠的 2 的幂长度区间,并使用可结合的聚合运算。这是数据结构预处理换取重复查询速度的经典范式。

下一课(2026-11-16,第 28 课):第 4 周综合考核与复习。 综合考查 Bellman–Ford、Dijkstra、Johnson、MST 交换论证和今天的倍增路径查询;第 5 周转入网络流与匹配。

九、四级自测(共 100 分;首次不给答案)

前三题客观判分,最后一题开放推导。课堂只提供答案中立的提示;标准答案、解析和评分细则仅放在对应的互动测验 JSON 中。

Lv1|倍增摘要不变量|15 分|预计 2 分钟|单选

树中 up[k][v] 表示向上恰好走 2^k 条边的祖先,mx[k][v] 表示这段路径上的最大边权。哪项严格正确?

A. mx[k][v] 必须存从根到 v 的所有边权之和,否则无法回答路径最大值。

B. 若两段长度 2^(k−1) 的祖先路径均存在,则 mx[k][v] 等于它们各自最大边权的最大值,up[k][v] 是两次祖先跳跃的结果。

C. 只要给每个顶点存一个直接父亲,就能在最坏 O(log n) 时间内查询任意路径最大边权。

D. 对有负权的树,使用 0 作为所有不存在路径段的最大值也不会影响结果。

中立提示:先画出长度 2^k 的向上路径怎样拆成连续两半,再考虑 max 操作的单位元。

Lv2|树路径倍增 Trace|20 分|预计 4 分钟|数值

以 A 为根的无向树有六条边:A–B(1)、B–C(4)、B–D(−2)、D–E(3)、D–F(5)、E–G(2)。用树路径最大值查询,计算 M(C,G)+M(A,E)(M 表示唯一路径上的最大边权),只提交数值,可附 LCA 与上跳过程。

中立提示:先用深度差对齐 C 和 G;两端最终在何处汇合?A 到 E 又需经过哪些边?

Lv3|查询边界、复杂度和 MST 唯一性|25 分|预计 4 分钟|多选

关于静态无向加权树的二进制提升,以及已知 MST T 的非树边换边判据,下列哪些说法成立?(多选)

A. 预处理祖先和最大边表需 O(n log n) 时间与空间;单次 LCA 加路径最大值查询最坏 O(log n),可以包含负权边。

B. 如果所有树边权重都小于 0,将路径最大值累计器初始化为 0 仍然正确。

C. 对任意一棵生成树(即使不是 MST),所有非树边 e 的 (w(e)-M(e)) 都必定非负。

D. 如果 T 已知是 MST,则每条非树边 e 都满足 (w(e)>M(e)) 当且仅当 T 是唯一 MST。

中立提示:分别检查倍增层数、max 的初始化、非最优树能否通过换边变好,以及严格不等式代表什么。

Lv4|树上最大边查询与 MST 加速设计|40 分|预计 10 分钟|开放推导

给定一棵 n≥2 个顶点的静态无向加权树 T,边权可为负。(a)(10 分)设计基于 DFS 和二进制提升的 up[k][v]、mx[k][v] 预处理,处理祖先不存在的情况;(b)(12 分)给出返回 LCA(u,v) 与 M(u,v) 的 O(log n) 查询伪代码,并使用“2^k 段摘要”及“已走路径分解”两个不变量证明正确性;(c)(10 分)推导预处理、单次查询的最坏时间及空间界。若 T 是某连通图 G 的已知 MST,解释如何在 O(m log n) 查询时间内检测唯一性,并在唯一时求严格次小生成树权重;(d)(8 分)给出将最大值初始化为 0 导致负边查询错误的最小反例,并说明 u=v、森林跨分量查询、树的边权动态改变时的处理边界。

中立提示:预处理归纳时,将 2^k 条边拆成两段各 2^(k−1) 条边。查询证明时,分别跟踪已经计入答案的路径边和尚未处理的路径边。MST 的结论须明确前提是 T 已经最优。

十、提交与反馈

回复 Lv1:选项;Lv2:数值与上跳过程;Lv3:全部正确选项;Lv4:(a)–(d) 的证明。我会按 15/20/25/40 分逐题批改:80–100 分进入第 4 周综合复习;60–79 分补一题倍增或 MST 换边练习;低于 60 分先复习“2 的幂路径摘要”和 LCA 不变量。补练不改变原定课号。