思路与算法

用Gomory-Hu割树表示无向图全部点对最小割。初始每个非根点父亲为0；依次求s到parent[s]的单位容量最大流，取残量源可达侧调整未处理点的父亲，必要时交换父边及割值。最终割树任意两点路径上的最小边权就是两点最大流。把树边按权从大到小用并查集合并，跨块点对的最小割就是当前边权，累加wsizeAsizeB。

正确性说明

无向最大流最小割定理把点对最大流转成割值。Gomory-Hu每次用一个真实最小割细分当前父子簇；割的次模性允许把既有最小割与新割解交而保持已求割值，故按源侧改父亲和父边交换后，处理过的割仍可由树边表示。n-1次后得到路径最小边等于任意点对最小割的割树。降序并查集第一次把两点连通时，当前边是它们树路径的最小权，恰计一次该点对。

复杂度

度数≤3保证每次最大流≤3，整数增广至多3次；每次残量搜索O(n+m)，总O(n(n+m)+n log n)时间、O(n+m)空间，包含每次重建残量图和所有数组初始化。

易错点

无向单位边用初始双向容量1的一对残量边表示；不能把一次单源流当成所有点对答案。断开点对流量0，最后仍可用0权割树边连接。64位保存总和，3000点上界可检验。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to, rev, cap;
};
struct Flow {
    int n;
    vector<vector<Edge>> g;
    vector<int> lev, it;
    Flow(int n) : n(n), g(n), lev(n), it(n) {
    }
    void add(int a, int b) {
        g[a].push_back({b, (int)g[b].size(), 1});
        g[b].push_back({a, (int)g[a].size() - 1, 1});
    }
    bool bfs(int s, int t) {
        fill(lev.begin(), lev.end(), -1);
        vector<int> q{s};
        lev[s] = 0;
        for (int i = 0; i < (int)q.size(); i++)
            for (auto e : g[q[i]])
                if (e.cap && lev[e.to] < 0) {
                    lev[e.to] = lev[q[i]] + 1;
                    q.push_back(e.to);
                }
        return lev[t] >= 0;
    }
    int dfs(int u, int t, int f) {
        if (u == t)
            return f;
        for (int &i = it[u]; i < (int)g[u].size(); i++) {
            Edge &e = g[u][i];
            if (e.cap && lev[e.to] == lev[u] + 1) {
                int got = dfs(e.to, t, min(f, e.cap));
                if (got) {
                    e.cap -= got;
                    g[e.to][e.rev].cap += got;
                    return got;
                }
            }
        }
        return 0;
    }
    int run(int s, int t) {
        int f = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            int v;
            while ((v = dfs(s, t, 4)))
                f += v;
        }
        return f;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    for (auto &e : edges) {
        cin >> e.first >> e.second;
        --e.first;
        --e.second;
    }
    vector<int> par(n), value(n);
    for (int s = 1; s < n; s++) {
        Flow f(n);
        for (auto e : edges)
            f.add(e.first, e.second);
        int t = par[s], v = f.run(s, t);
        for (int i = s + 1; i < n; i++)
            if (par[i] == t && f.lev[i] >= 0)
                par[i] = s;
        if (f.lev[par[t]] >= 0) {
            par[s] = par[t];
            par[t] = s;
            value[s] = value[t];
            value[t] = v;
        } else
            value[s] = v;
    }
    vector<array<int, 3>> tree;
    for (int i = 1; i < n; i++)
        tree.push_back({value[i], i, par[i]});
    sort(tree.rbegin(), tree.rend());
    vector<int> p(n), sz(n, 1);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    };
    long long ans = 0;
    for (auto e : tree) {
        int a = find(e[1]), b = find(e[2]);
        ans += 1LL * e[0] * sz[a] * sz[b];
        p[a] = b;
        sz[b] += sz[a];
    }
    cout << ans << "\n";
}