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.
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.
- Mathematical explanation of Leetcode question: Container With Most Water
- How to check a point is inside an ellipsoid with orientation?
- algorithm to trace border in 2D array
- Red Black Tree Black Height Increase after Insertion
- Coin Change II : To take a value or not to
- Logic to implement to get maximum points
- Generate all strings under length N in C
- Algorithm to extract overlapping range
- Merging two sorted linked lists
- Median of two sorted-arrays algorithm for O(log(m+n))
- Calculating new longitude, latitude from old + n meters
- Calculation of Average Queue Length in a Simple Queueing Model
- what is the most efficient way to gather all points at a certain height?
- Does a recursive segment tree require more space than an iterative one?
- Tarjan Algorithms for SCC
- Is there a balanced BST with each node maintain the subtree size?
- Sort on a string that may contain a number
- Optimally counting number of nodes in a complete binary tree
- Fraction to Recurring Decimal
- Quicksort with Python
- What is the optimal algorithm for the game 2048?
- Asteroid Mining - Dynamic Programming problem
- Optimize performance for dense ranking algo
- Looking for a sort algorithm with as few as possible compare operations
- How to remove a line by its number from file without rewriting file python
- The output gives the same result
- Radix sort slower than expected compared to standard sort
- How to find minimum pairing cost? (Any Language)
- Algorithm to minimize the number of printing plates when printing sheets of stickers
- Travel from city 1 to city n, visiting at least 3 odd cities