从一个节点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)
Given a connected undirected graph having N nodes (1 <= N <= 2 * 10^5) and N-1 edges. Let's define a function F(a,b), where F(a, b) is equal to the maximum edge weight in the path from a to b. How do we find the sum of the F(a, b) for all a, b such that 1 <= a, b <= N (mod 10^9 + 7)
示例图
< img src = https://i.stack.imgur.com/XvWVc.png alt =在此处输入图片描述>
F( a,b)等于从a到b的路径中的最大边缘权重。
F(a, b) is equal to the maximum edge weight in the path from a to b.
F(1,2)= 2
F(1, 2) = 2
F(1,3)= 2
F(1, 3) = 2
F(1,4)= 4
F(1, 4) = 4
F(1,5)= 4
F(1, 5) = 4
F(2,3)= 1
F(2, 3) = 1
F (2,4)= 4
F(2, 4) = 4
F(2,5)= 4
F(2, 5) = 4
F(3,4 )= 4
F(3, 4) = 4
F(3,5)= 4
F(3, 5) = 4
F(4,5)= 3
F(4, 5) = 3
所有对中的F的总和等于32。
Sum of F over all pairs is equal to 32.
推荐答案
我们可以为此使用Kruskal的MST算法的一种变体(Kruskal是按增量对边进行排序重量,贪婪地插入那些没有循环的数据(借助不相交的集合数据结构)。将运行总和初始化为零;每当我们将大小为S1的不相交集(此信息作为按大小进行并集的不相交集数据结构的副产品)和大小为S2的不相交集通过权重w合并在一起时,将S1 * S2 * w添加到总和为10 ^ 9 + 7。
We can use a variant of Kruskal's MST algorithm for this (Kruskal is sort edges by increasing weight, greedily insert the ones that don't make a cycle with the aid of a disjoint set data structure). Initialize a running sum to zero; whenever we merge a disjoint set of size S1 (this information is available as a byproduct of a disjoint set data structure that does union by size) with a disjoint set of size S2 via an edge of weight w, add S1*S2*w to the sum mod 10^9 + 7.
这篇关于从一个节点A到节点B的最大边缘权重的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!