最小生成树的有根树分解（Rooted Tree Decomposition）

一、题目描述

在最小生成树（Minimum Spanning Tree, MST）问题中，给定一个连通无向图 G=(V, E)，边权为整数，我们熟知 Kruskal 和 Prim 算法可以高效地找到一棵最小生成树 T。现在，我们想对最小生成树 T 进行一种特殊的分解，称为“有根树分解”。具体来说，我们首先为最小生成树 T 选择一个根节点 r，将其转化为一棵有根树。然后，我们希望将 T 分解成一组“分支”（branch），每个分支是 T 中从某个节点到其后代节点的一条路径，且满足以下条件：

1. 树 T 中的每条边恰好属于一个分支。
2. 每个分支是一个“垂直”路径（从某个节点到其后代节点的一条简单路径，可以是一个节点自身，此时路径长度为0）。
3. 不同分支在树 T 上的“最低公共祖先”（LCA）必须是某个分支的端点。

这个分解被称为“有根树分解”或“垂直路径分解”。我们的任务是，给定一棵最小生成树 T 和根节点 r，设计一个算法，高效地构造出满足上述条件的一个分解，并且使得分解中的分支数量尽可能少（可以证明，在满足条件的前提下，分支数量是唯一确定的）。然后，利用这个分解，可以回答一类关于最小生成树上的路径查询，例如：查询任意两个节点在最小生成树 T 上的唯一路径上，边权的最大值是多少？

二、解题思路

首先，我们需要理解这个分解的目的。它本质上是将一棵有根树“剖分”成若干从祖先指向后代的垂直路径。这与数据结构中“树链剖分”（Heavy-Light Decomposition, HLD）的思想有相似之处，但要求略有不同：树链剖分的目标是保证从根到任意节点的路径能被划分为 O(log n) 条链，以支持路径查询/更新；而本问题中的分解条件（特别是条件3）是为了后续处理特定类型查询（如路径最大边权查询）时，可以将查询转化为对 O(log n) 个分支的查询。

实际上，可以证明，满足上述三个条件，且分支数量最少的分解，等同于按照以下规则构造的分解：从根节点 r 开始，对每个节点 u，如果 u 有至少一个子节点，则选择它的一个“重子节点”（heavy child），并将边 (u, heavy_child) 与 heavy_child 所在的分支合并；u 的其他每个子节点 v（即轻子节点），则各自开启一个新的分支，起点为 v（或者说，边 (u, v) 作为一个新分支的开始）。这里“重子节点”定义为子树大小最大的子节点（如果多个，任选一个）。

这样构造出的分支被称为“重路径”（heavy paths）。这就是著名的“树链剖分”（Heavy-Light Decomposition, HLD）中划分“重链”的过程。可以验证，它满足题目中分解的三个条件，并且分支数量最少（等于轻边数量+1，因为每条轻边会开启一个新分支，根节点自身也算一个分支起点）。因此，我们的算法本质上就是实现树链剖分中对树的链划分部分。

之后，利用这个分解，如果我们想查询树 T 上任意两点 u, v 之间路径上的最大边权，我们可以通过求出 u 和 v 的 LCA，然后将 u 到 LCA 的路径，以及 v 到 LCA 的路径，分别分解成若干条“垂直路径”（即我们分解得到的分支），然后在每条分支内部，由于分支是一条从上到下的路径，我们可以用线段树、BIT 等数据结构维护其边权的最大值（注意每条分支需要建立自己的数据结构，且需要记录每个节点在分支内的顺序位置），最后合并这些分支查询的结果，取最大值即可。一次查询的时间复杂度为 O(log² n)，因为每条路径会被分解成 O(log n) 条分支，每查询一条分支需要 O(log n) 时间。

三、解题步骤

我们分为两个主要部分：A. 构造有根树分解（即重链剖分）。B. 基于分解，回答路径最大边权查询。

A. 构造有根树分解（重链剖分）

输入：最小生成树 T（n 个节点，n-1 条边，边权已知），根节点 r。
输出：每个节点所属的“分支”（重链）的编号，以及节点在其所在分支内的位置（深度，从链顶向下递增）。

步骤1：以 r 为根，进行深度优先搜索（DFS），计算出每个节点的父节点 parent[u]、深度 dep[u]、子树大小 size[u]。

def dfs1(u, p):
    parent[u] = p
    size[u] = 1
    for v, w in adj[u]:  # adj[u] 是邻接表，包含 (邻居, 边权)
        if v != p:
            dep[v] = dep[u] + 1
            # 可以同时存储边权，例如 weight[v] = w 表示从父节点到 v 的边权
            dfs1(v, u)
            size[u] += size[v]

在第一次 DFS 中，我们也可以记录每个节点的“重子节点” heavy[u]：即 u 的子节点中，size 最大的那个。如果有多个最大，任选一个。

步骤2：进行第二次 DFS，目的是给每个节点分配其所在的重链编号 chain_id[u]，以及节点在重链中的位置 position[u]（从链顶开始为0递增）。同时，我们需要记录每条重链的链顶节点 chain_top[chain_id]，以及每条重链包含的节点列表（方便后续建立线段树等数据结构）。

def dfs2(u, p, top, current_chain_id):
    chain_id[u] = current_chain_id
    position[u] = len(chain_nodes[current_chain_id])  # 在链中顺序位置
    chain_nodes[current_chain_id].append(u)  # 存储链中节点，按深度递增
    chain_top[current_chain_id] = top  # 这条链的顶端节点是 top

    if heavy[u] != -1:  # 如果 u 有重子节点
        # 重子节点与 u 在同一个重链上
        dfs2(heavy[u], u, top, current_chain_id)
    # 处理轻子节点
    for v, w in adj[u]:
        if v != p and v != heavy[u]:
            # 每个轻子节点开启一个新的重链，链顶就是 v 自身
            new_chain_id = next_chain_id
            next_chain_id += 1
            dfs2(v, u, v, new_chain_id)

初始调用：dfs2(r, -1, r, 0)，其中 next_chain_id 初始为 1。

经过这两次 DFS，我们得到了树的重链剖分。每条重链就是一个“分支”（垂直路径），满足分解条件。可以证明分支（重链）数量 = 轻边数量 + 1 ≤ n，且从根到任意节点的路径上，切换重链的次数（即经过的轻边数量）是 O(log n) 的，因为每经过一条轻边，子树大小至少减半。

B. 基于分解回答路径最大边权查询

查询：给定树上两个节点 u 和 v，求它们之间唯一路径上边权的最大值。

思路：将 u 到 v 的路径分解为若干条重链（分支）的片段，对每个片段查询最大值，然后合并。

步骤1：我们需要建立数据结构来维护每条重链内部边权的最大值。由于每条重链是一条从链顶到链底的路径，节点在链中按深度递增排列。我们可以为每条重链建立一个线段树（或 Fenwick Tree 等，但查询最大值用线段树更方便），线段树的下标对应节点在链中的位置 position[u]。线段树叶节点存储对应节点与其父节点之间边的边权（注意根节点没有父节点，其边权可设为 -∞ 或跳过）。由于我们之前用 weight[v] 记录了从 parent[v] 到 v 的边权，所以对于链中位置为 i 的节点 u（i>0），其边权为 weight[u]；对于链顶节点（i=0），没有向上的边，可以忽略或赋一个极小值。

步骤2：查询函数 query_path(u, v) 的实现。
算法类似于树链剖分中路径查询的“爬升”过程：

def query_path(u, v):
    ans = -inf
    # 当 u 和 v 不在同一条重链上时，将深度较大的链向上“跳”
    while chain_id[u] != chain_id[v]:
        # 比较两条链的链顶的深度，选择深度大的那个链
        if dep[chain_top[chain_id[u]]] > dep[chain_top[chain_id[v]]]:
            # 此时，u 所在的链更深。查询 u 到其链顶的这一段路径
            # 注意：查询的是从 u 到 chain_top[chain_id[u]] 的路径上的最大边权
            # 线段树查询的是链上区间 [position[chain_top[chain_id[u]]], position[u]]
            # 由于链顶的 position 是 0，u 的 position 更大
            left_pos = position[chain_top[chain_id[u]]]
            right_pos = position[u]
            ans = max(ans, segment_tree_query(chain_id[u], left_pos, right_pos))
            # 然后 u 跳到链顶的父节点
            u = parent[chain_top[chain_id[u]]]
        else:
            # 对 v 做类似操作
            left_pos = position[chain_top[chain_id[v]]]
            right_pos = position[v]
            ans = max(ans, segment_tree_query(chain_id[v], left_pos, right_pos))
            v = parent[chain_top[chain_id[v]]]
    # 最后 u 和 v 在同一条重链上
    # 假设现在 u 和 v 是同一链上的两个节点，且 dep[u] <= dep[v]（否则交换）
    if dep[u] > dep[v]:
        u, v = v, u
    # 此时查询链上 (u, v] 的边权最大值（因为 u 是 LCA，从 u 的子节点到 v 的路径）
    if u != v:  # 如果 u != v，则区间为 (position[u], position[v]]
        # 注意：u 是 LCA，我们只需要查询 u 的子节点到 v 这段路径的边权
        # 在链上，位置 position[u] 对应的节点是 u，它的下一条边对应其子节点，位置为 position[u]+1
        left_pos = position[u] + 1
        right_pos = position[v]
        ans = max(ans, segment_tree_query(chain_id[u], left_pos, right_pos))
    return ans

注意：线段树存储的是边权，但位置 i 存储的是从链中第 i-1 个节点到第 i 个节点的边权（i≥1）。因此，查询区间 [L, R] 时，实际上查询的是位置 L 到 R 的边权（即从链中第 L 个节点到第 R 个节点的路径上的边，注意是链内部的连续边）。在实现时，需要仔细处理节点与边的对应关系，通常我们让线段树的第 i 个叶节点（i 从 0 开始）对应链中位置为 i 的节点到其父节点的边（如果 i=0，则对应一个不存在的边，可设为 -∞）。另一种常见做法是，在 DFS 时，将边权赋给深度较大的节点，查询时避开 LCA 对应的节点。

四、复杂度分析

• 预处理（两次 DFS + 构建每条链的线段树）：O(n) 时间遍历树，O(n log n) 时间构建所有线段树（因为总节点数为 n，构建线段树的总复杂度为 O(n log n)），空间 O(n)。
• 每次查询：while 循环每次跳转都会跳到一条更浅的重链，由于重链数量 O(log n)，循环次数 O(log n)。每次循环中进行一次线段树区间查询，复杂度 O(log n)。因此，单次查询总复杂度 O(log² n)。

五、总结

本题将最小生成树的有根树分解问题转化为经典的重链剖分（HLD）构造。通过两次 DFS 可以完成对树的链划分，满足题目中的三个分解条件。基于这个分解，我们可以利用线段树等数据结构高效支持树上路径的最大边权查询。整个过程展示了如何将一棵静态树进行路径分解，并将路径查询转化为 O(log n) 个区间查询，是树链剖分的典型应用。