algorithm - 从一个节点 A 到节点 B 的最大边权重

Question

给定一个有N个节点 (1 <= N <= 2 * 10^5) 和N-1 条边的连通无向图。让我们定义一个函数F(a,b)，其中F(a, b)等于从a到b的路径中的最大边权重。我们如何找到所有a , b的F(a, b)的总和，使得1 <= a , b <= N (mod 10^9 + 7)

示例图

F(a, b) 等于从 a 到 b 的路径中的最大边权重。

F(1, 2) = 2

F(1, 3) = 2

F(1, 4) = 4

F(1, 5) = 4

F(2, 3) = 1

F(2, 4) = 4

F(2, 5) = 4

F(3, 4) = 4

F(3, 5) = 4

F(4, 5) = 3

所有对的 F 之和等于 32。

Answer 1

为此，我们可以使用 Kruskal 的 MST 算法的变体（Kruskal 通过增加权重对边进行排序，借助不相交的集合数据结构贪婪地插入不形成循环的边）。将运行总和初始化为零；每当我们通过权重为 w 的边将大小为 S1 的不相交集（此信息作为不相交集数据结构的副产品提供）与大小为 S2 的不相交集合并时，将 S1*S2*w 添加到总和 mod 10^9 + 7。