Вам дан неорентированный взвешанный связанный граф из n вершин и m ребер. Назовем стоимостью пути значение максмимума среди весов ребер на пути. Пусть d(v,u) – это минимальная стоимость пути начинающегося в v и заканчивающегося в u. Посчитайте значение ∑1≤v<u≤nd(v,u) – сумма d(v,u) по всем парам (v,u).
В первой строке даны числа n(2≤n≤10^5) и m(n−1≤m≤3⋅10^5 – количество вершин и количество ребер.
В следующих m даны si, ti, wi(1≤si,ti≤n,1≤wi≤10^6) – описание ребра соеденяющего вершины si и ti с весом wi. Гарантируется что si≠ti.
Гарантируется что от каждой вершины можно добраться до любой другой двигаясь по рербам графа.
- Примеры
- входные данные
- 3 3
- 1 2 5
- 1 3 1
- 2 3 4
- выходные данные
- 9
Источник задачи?
Сортируешь рёбра по весу, идёшь в порядке возрастания и добавляешь рёбра в граф.
Пусть ты сейчас добавляешь ребро u v w, если вершины u и v уже связаны то ничего не делаешь, если они не связаны то добавляешь к ответ sz(u) * sz(v)* w, где sz(x) — количество вершин в компоненте в которой находится x, sz можно считать за время O(a(n). И соединяешь вершины u и v
Почему это работает? Пусть ребро u v w минимальное максимальное ребро на пути. Тогда если компоненты вершин u и v одинаковые то эти вершины уже были соединены ребром вес которого меньше или равен w, так как они были соединены ребром которое идет раньше в отсортированном массиве. Если они не связаны то на любом пути который начинается в первой компоненте и заканчивается во второй минимальный максимальным ребром будет это ребро, очевидно что все пути из первой компоненты в вторую компоненту проходят через это ребро(так как если бы был другой проход то вершины u и v были бы связаны), и понятно что данное ребро максимально так как все добавленные до этого ребра имеют вес меньше или равный w.