牛牛题。
先讲我自己想到的部分。
首先最大流肯定不好做，做最小割。
然后显然有最小割树。
但现在问题出在如何求最小割上。
一个很大的问题是，你求最小割至少都要考虑所有的即一定是 $\Omega(n)$。
然而如果这样时间复杂度就已经爆了。
我一直的思路都是用数据结构扫描线啊啥的维护发现很难做。（也许可以做？我好像看到有人用 DS，有可能是把不同的步骤在 DS 上合在一起吧。）
然后题解做了个很厉害的事情，他说：平面图我们要想到对偶图。
好的我们考虑他的对偶图。
我们考虑我们求一次最小割，是在做什么事情。
我们发现在对偶图上就是把 $s$ 和 $t$ 伸两条射线出去，然后做对偶图，就是上下两个无限平面的最短路。
如果只是想到这里，我们只是得到了一个 $\Omega(n\log n)$ 的算法，但其实无论如何，这已经优于我们的朴素 DS 了（而且我们的朴素 DS 很难写）。
我们想一下我们的根本诉求是什么，我们的根本诉求是，把这个最小割树转化为其他东西，而不是直接求最小割（因为这样一定会爆）。
但若是我们继续想。我们递归之后做的是什么呢，我们做的其实是把左右分成两半，然后对于左边，就把右边整个缩为一个点，右边同理。
我们首先就是想到，我们无论怎么分，实际上最多只有 $n$ 个无限平面，我们干脆提前分好，然后我们发现我们变成了是选两个无限平面使得最短路最短。
实际上这就是在树上找最近的两个叶子。
我们试图继续用这种找两个的方式选，然后我们想到我们既然不要这两个点，那我们把这俩合起来。我们看其他最小的两个叶子。
Creatively，我们发现我们在做 kruskal。
然后我们不想做 kruskal。
面对 MST 最好用的就是 boruvka。
然后我们使用 boruvka。
我们如何找树上每个叶子最近的不同块的叶子呢。
我们可以使用 DP，从下到上做一遍，从上到下做一遍，记录最小次小即可。
然后我们就建出来了合并无限平面的树。
但我们要得是最小割树。
于是我们再对偶回去即可。
就这个题最本质的 idea 是，你可以“发现你在做一个经典问题然后换一种解法”。比如把 kruskal 换成 boruvka。
这仍然是灵活迁用，更本质的来说，这是把方法之间建立活的联想连接，而不是感觉连接。这对发散性思维有很高的要求。、
然后其他一些重要的是平面图用对偶图。
还有就是提前处理的思想，把无限平面分成 $n$ 个也可能是一个卡点。
还有呢，就是一个贯彻思想的做法。比如你第一下找的是最近叶子，那你肯定也希望接下来也是最近叶子。
透过现象看本质。