Максимальный вес ребра от одного узла A до узла B

Question

Для связанного неориентированного графа, имеющего N узлов (1 <= <strong>N <= 2 * 10 ^ 5) и <strong>N-1 ребер.Давайте определим функцию F (a, b) , где F (a, b) равно максимальному весу ребра на пути от a до б .Как нам найти сумму F (a, b) для всех a , b , такую, что 1 <= <em>a , b <= <strong>N (мод 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.

Answer 1

Для этого мы можем использовать вариант алгоритма MST Крускала (Крускал сортирует ребра, увеличивая вес, жадно вставляя те, которые не делают цикл, с помощью непересекающейся структуры данных набора). Инициализировать текущую сумму до нуля; всякий раз, когда мы объединяем непересекающийся набор размера S1 (эта информация доступна как побочный продукт структуры данных непересекающегося набора, которая объединяет по размеру) с непересекающимся набором размера S2 через ребро веса w, добавьте S1 * S2 * w к сумма мод 10 ^ 9 + 7.