最小割树

最小割树是指构造一颗树，使得任意 \(u, v\) 的最小割等于树上两点之间的最小边权，且 \(u, v\) 的割边方案就是这条边两端割边方案。这里我们不考虑方案相同，只要求答案相同，这个叫等价流树。

构造：选取任意两点 \(u, v\)，连 \((u, v, f(u, v))\) 的边。则整个点集被分为两个联通块 \(S\) 和 \(T\)，递归构建即可。

Lemma 1 : 任意 \(x \in S, y \in T\)，有 \(f(u, v) \ge f(x, y)\)。

Proof 1 : 容易发现 \(f(u, v)\) 是 \(f(x, y)\) 的一种方案。根据这个引理构造的正确性显然。

Lemma 2 : 任意三个点 \(u, v, w\)，有 \(|\{f(u, v), f(u, w), f(v, w)\}| \le 2\) 。

Proof 2 : 假设 \(f(u, v)\) 最大。则在 \(f(u, w)\) 和 \(f(v, w)\) 中 \(u, v\) 都在同一侧，则 \(f(u, w) = f(v, w)\)。

Lemma 3 : 任意三个点 \(u, v, w\)，有 \(f(u, v) \ge \min \{ f(u, w), f(v, w) \}\)。

Proof 3 : 假设 \(f(u, v)\) 为严格最小值。此时 \(w\) 既会在 \(u\) 一侧也会在 \(v\) 一侧，否则 \(f(u, w)\) 或者 \(f(v, w)\) 会等于 \(f(u, v)\)。