Дан связанный неориентированный граф, имеющий узлы N (1 <= N <= 2 * 10 ^ 5) и ребра N-1. Определим функцию F (а, б), где F (а, б) равно максимальному весу ребра на пути от а до б. Как найти сумму F (а, б) для всех а, б, таких что 1 <= а, б <= N (mod 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.
На самом деле у меня есть решение n ^ 2, в котором я запускал dfs из каждого узла, тем самым вычисляя ответ для каждой пары узлов. Не могу найти оптимального решения.
Покажите, пожалуйста, свой алгоритм. Возможно, мы сможем его улучшить.
Мы можем использовать для этого вариант алгоритма MST Краскала (Краскал сортирует ребра по увеличению веса, жадно вставляет те, которые не образуют цикл, с помощью несвязной структуры данных). Инициализировать текущую сумму до нуля; всякий раз, когда мы объединяем непересекающийся набор размера S1 (эта информация доступна как побочный продукт структуры данных непересекающегося набора, которая объединяет по размеру) с непересекающимся набором размера S2 через ребро веса w, добавляем S1 * S2 * w к сумма по модулю 10 ^ 9 + 7.
В частности, это работает, потому что каждый раз, когда мы добавляем ребро, это обязательно ребро с максимальным весом, соединяющее узлы с противоположных сторон, потому что мы добавляем ребра в порядке увеличения веса.
что ты уже испробовал?