从一个节点 A 到节点 B 的最大边权重
Maximum edge weight from one node A to node B
给定具有 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。
我们可以为此使用 Kruskal 的 MST 算法的变体（Kruskal 通过增加权重对边进行排序，借助不相交的集合数据结构贪婪地插入不构成循环的边）。将 运行 和初始化为零；每当我们通过权重 w 的边将大小为 S1 的不相交集（此信息可作为按大小并集的不相交集数据结构的副产品提供）与大小为 S2 的不相交集合并时，将 S1*S2*w 添加到总和 mod 10^9 + 7.
给定具有 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。
我们可以为此使用 Kruskal 的 MST 算法的变体（Kruskal 通过增加权重对边进行排序，借助不相交的集合数据结构贪婪地插入不构成循环的边）。将 运行 和初始化为零；每当我们通过权重 w 的边将大小为 S1 的不相交集（此信息可作为按大小并集的不相交集数据结构的副产品提供）与大小为 S2 的不相交集合并时，将 S1*S2*w 添加到总和 mod 10^9 + 7.