求无向树中所有节点对路径最大边权之和（模1e9+7）

嘿，这个问题直接枚举所有节点对肯定行不通——毕竟N能达到2×10^5，O(N²)的时间复杂度绝对会超时。咱们换个更高效的思路：计算每条边对总答案的贡献，把所有边的贡献加起来就是最终结果。

核心思路 #

对于树中的每条边e（权值为w），我们只需要找出有多少个节点对(a,b)，使得它们的路径上的最大边权恰好是w。然后总答案就是所有边的w × 对应节点对数量的总和。

为什么这个思路可行？因为树是连通无向图，任意两个节点之间有且仅有一条路径。我们可以借鉴Kruskal算法的思想：

1. 把所有边按权值从小到大排序。
2. 当处理边e时，这条边连接的两个连通分量在之前是完全分离的（因为之前处理的边权都比w小，还没把这两个分量连起来）。
3. 所有跨这两个分量的节点对，它们的路径必须经过e，而且e是这条路径上的最大边（路径上其他边的权都比w小）。

假设这两个分量的大小分别是s和N-s，那么符合条件的无序节点对数量就是s × (N - s)（示例中统计的是无序对的总和，若需统计有序对则是2 × s × (N - s)）。

具体实现步骤 #

我们用**并查集（Union-Find）**来高效维护连通分量的大小：

1. 收集所有边，每条边记录两个端点和权值。
2. 按边的权值从小到大排序。
3. 初始化并查集：每个节点单独作为一个分量，大小为1。
4. 初始化总答案为0，模数MOD = 10^9 + 7。
5. 遍历每条边：
   • 找到两个端点所在分量的根节点。
   • 如果根节点不同（说明两个分量未连通）：
     • 获取两个分量的大小s1和s2。
     • 计算当前边的贡献：(w * s1) % MOD，再乘以s2后取模，加到总答案中（总答案也要取模）。
     • 合并这两个分量，更新分量的大小。
6. 遍历完成后，总答案就是最终结果。

代码示例（Python） #

MOD = 10**9 + 7

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))  # 节点编号从1开始
        self.size = [1] * (size + 1)
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return 0  # 已经连通，无贡献
        # 按大小合并，把小的合并到大的下面
        if self.size[x_root] < self.size[y_root]:
            x_root, y_root = y_root, x_root
        self.parent[y_root] = x_root
        res = self.size[x_root] * self.size[y_root]
        self.size[x_root] += self.size[y_root]
        return res

def calculate_total_F(N, edges):
    # 按边权从小到大排序
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(N)
    total = 0
    for u, v, w in edges:
        cnt = uf.union(u, v)
        if cnt > 0:
            total = (total + w * cnt) % MOD
    return total

# 示例测试
N = 5
edges = [
    (1, 2, 2),
    (2, 3, 1),
    (1, 4, 4),
    (4, 5, 3)
]
print(calculate_total_F(N, edges))  # 输出32，和示例一致

示例验证 #

我们用题目中的示例来验证：

• 边按权值排序后为：(2,3,1), (1,2,2), (4,5,3), (1,4,4)
• 处理(2,3,1)：分量大小1和1，贡献1×1×1=1，总答案=1
• 处理(1,2,2)：分量大小1和2，贡献2×1×2=4，总答案=5
• 处理(4,5,3)：分量大小1和1，贡献3×1×1=3，总答案=8
• 处理(1,4,4)：分量大小3和2，贡献4×3×2=24，总答案=32

完全匹配示例的结果！

内容的提问来源于stack exchange，提问作者Deepak Chaudhary