vi. Gomory-Hu Tree

For an undirected graph there is a weighted tree on the same vertices such that for every pair $u,v$ the minimum $u$–$v$ cut $\lambda (u,v)$ equals the minimum edge weight on the tree path, and removing that edge splits the vertices into an actual minimum $u$–$v$ cut. It takes $n-1$ max flows (Gusfield’s version needs no contraction). Consequences: at most $n-1$ distinct pairwise min-cut values, all-pairs queries by path minimum, edge connectivity = lightest tree edge. No such tree exists for directed graphs.

vector<array<ll, 3>> gomoryHu(int n, const vector<array<ll, 3>>& E) {   // {u, v, w}; returns tree edges {v, p, cut}
    vector<int> p(n, 0); vector<ll> fl(n);
    for (int s = 1; s < n; s++) {
        int t = p[s]; Dinic D(n);
        for (auto [u, v, w] : E) D.addEdge(u, v, w, w);
        ll f = D.maxflow(s, t); fl[s] = f;
        for (int i = 0; i < n; i++) if (i != s && D.sourceSide(i) && p[i] == t) p[i] = s;
        if (D.sourceSide(p[t])) p[s] = p[t], p[t] = s, fl[s] = fl[t], fl[t] = f;   // keeps the cut property
    }
    vector<array<ll, 3>> tree;
    for (int v = 1; v < n; v++) tree.push_back({v, p[v], fl[v]});
    return tree;
}

Dropping the last line of the loop (the swap) and the i < s updates still gives a correct flow-equivalent tree (right values, but tree-edge cuts may not be the real cuts). Swap Dinic for push–relabel on dense graphs.

Using the tree

• Query $\lambda (u,v)$: path minimum (binary lifting, or $O(n)$ DFS per query for small $n$).
• Sum of $\lambda$ over all pairs: sort tree edges by decreasing weight and merge with a DSU; an edge joining components of sizes $a,b$ contributes $w\cdot a\cdot b$.
• Count pairs with $\lambda \ge k$: the same DSU, stopping at weight $k$.
• Minimum $k$-cut approximation: remove the $k-1$ lightest tree edges; within a factor $2-2/k$.
• Minimum cut separating a vertex set $T$ (Steiner cut): the lightest tree edge whose removal splits $T$.

ll allPairsMinCutSum(int n, vector<array<ll, 3>> tree) {
    sort(all(tree), [](auto& a, auto& b) { return a[2] > b[2]; });
    DSU d(n); ll s = 0;
    for (auto [u, v, w] : tree) s += w * d.size(u) * d.size(v), d.unite(u, v);
    return s;
}

Proof: path minimum equals $\lambda$ given the cut property

Triangle inequality: $\lambda (a,c)\ge \min (\lambda (a,b),\lambda (b,c))$, because a minimum $a$–$c$ cut separates $b$ from $a$ or from $c$, and is then at least that pair’s minimum. Along any path this gives $\lambda (u,v)\ge$ the minimum of $\lambda$ over consecutive pairs. Cut property: every tree edge $(x,y)$ has weight $\lambda (x,y)$, and the two components of the tree without it form a cut of exactly that weight. Then along the tree path, $\lambda (u,v)\ge {\min }_{\text{edges}}\lambda (x,y)$ = min edge weight, and the lightest edge’s fundamental cut separates $u$ from $v$ with that weight, so $\lambda (u,v)\le$ it. Equality, and that cut is a minimum $u$–$v$ cut. The DSU sum then follows: when the edge of weight $w$ merges components $A$ and $B$, every earlier edge is at least $w$, so all pairs across have path minimum exactly $w$.

Proof sketch: why the construction keeps the cut property

Uncrossing lemma. Let $X$ be a minimum $s$–$t$ cut ($s\in X$) and $u,v\in X$. Then some minimum $u$–$v$ cut lies inside $X$. Let $Y$ be any minimum $u$–$v$ cut; replacing $Y$ by its complement (and swapping $u,v$) we may assume $t\notin Y$. Cut functions are submodular: $c(X\cap Y)+c(X\cup Y)\le c(X)+c(Y)$. $X\cup Y$ contains $s$ but not $t$, so $c(X\cup Y)\ge c(X)$, giving $c(X\cap Y)\le c(Y)$; and $X\cap Y$ still contains exactly one of $u,v$. So contracting $\bar{X}$ to one vertex does not change $\lambda (u,v)$.

Gomory–Hu maintain a tree of super-vertices with the cut property. Splitting a super-vertex $S$ with $s,t\in S$: contract each subtree hanging off $S$ into one vertex (each lies on one side of a minimum cut of an earlier pair, so by the lemma $\lambda (s,t)$ is unchanged), find a minimum $s$–$t$ cut $X$, split $S$ into $S\cap X$ and $S\setminus X$, joined by an edge of weight $\lambda (s,t)$, and attach each hanging subtree to the side its contracted vertex fell on. The old edges keep their cuts (the subtrees moved as wholes) and the new edge’s fundamental cut is $X$. After $n-1$ splits every super-vertex is a single vertex.

Gusfield shows the contraction is unnecessary: by the lemma, a minimum $s$–$t$ cut computed in the uncontracted graph can be uncrossed, without changing its value or how it splits $S$, into one that keeps every hanging subtree on one side. The array $p$ stores the tree with each super-vertex represented by a star around one vertex; reassigning p[i] = s for the vertices of $s$‘s side, and the swap when the parent of $t$ falls on $s$‘s side, are exactly the split-and-reattach step expressed on that representation.