Maximum edge weight from one node A to node B

问题:

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)

Example figure

F(a, b) is equal to the maximum edge weight in the path from a to 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

Sum of F over all pairs is equal to 32.

回答1:

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.