首先一眼就要转对偶图。转完变成求对偶图上两个对应无限大半平面的点之间的最短路。

但是转完乍一看还是不会处理全局的 $\sum f(s,t)$。

回顾一下，平时处理全局最小割（最大流）是用最小割树做的：随便取源汇跑个最小割，把最小割作为一条边，然后把源点汇点的点集拿出来递归跑。

我们考虑也做类似的操作。但是推广遇到了一些问题。

首先就是，不同的源点汇点对应的半平面不一样，需要重新建边。我们直接在一开始就把外侧分成 $n$ 个无限大的平面，源汇变成了两个点集区间之间的最短路。

同时不难发现对偶图形如一棵 $n$ 个叶子的树。那么现在找最小割，其实就是找距离最近的一对叶子（虽然上面说的是任选一个最小割，但如果找的不是最近的叶子不一定是最小割）。

这对叶子之间的路径对应一个最小割，割开了这条路径两侧的点。按照最小割树的方法，接下来我们要递归到这条路径两侧继续找最短路了。

这样不断找最短路、划分、递归。直到最终 $n$ 个叶子都划分到一个单独的块里。

每条最短路在平面上分开了两个叶子集合。把最短路画到平面上，再做一个对偶，得到的就是最小割树了。对偶图里每条边的边权等于它对应的最短路长度。 其实很合理，在对偶图上跑出来的东西再对偶一下不就回去了吗。

所以现在我们就知道这个对偶图里的最小割树怎么做了。

但是问题是，每次跑一遍最短路还是太爆炸了。

这里又有一个很人类智慧的地方。我们发现这个最小割树其实就是：考虑构造一个 $n$ 个点的完全图，两点之间的边权为两个叶子在对偶图（树）上的距离。在这个完全图上跑 MST。

为什么呢？结合上面分析过的跑出最小割树的方式（每次取最短的最短路），我们从 kruskal 的角度解释。

因为 kruskal 每次都取的是最小的边（最小的最短路），我们只需要说明每次取的最短路画在图上不会 “穿过” 之前的边。而这是比较简单的。如果穿过了，从交点处把两条路径断开得到四个部分，顺次记为 $a,b,c,d$，设先找到的最短路为 $a+c$，后找到的最短路为 $b+d$。

因为在找 $b+d$ 的时候没有找到 $a+b,b+c,c+d,d+a$，所以 $b+d$ 比它们小。所以 $4(b+d)<(a+b)+(b+c)+(c+d)+(d+a)=2(a+b+c+d)$。移项可得 $b+d< a+c$。

但是因为 $a+c$ 在 $b+d$ 之前就被找到了，所以 $a+c\le b+d$，矛盾。

因此问题转化为：给定一棵树，构造一个完全图，每个点对应一个叶子，边权为叶子的距离，求这棵树的 MST。

求出 MST 之后，问题变成求每个点对路径上边权最小值的和。这个是简单的。

考虑怎么求 MST。完全图 MST 不难想到 boruvka 算法。考虑现在叶子有不同的颜色，怎么对每个叶子找到最近的不同色的叶子？类似换根 DP，从下到上做一遍求出子树内，再从上到下做一遍子树外，记录最近和次近的颜色即可。

于是就做完了，复杂度 $O(n\log n)$。