从一个节点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屋！