记 $g_i$ 表示割出 $|S|=i$ 所需要的最小最大割边，答案即为 $\min \dfrac {g_i}{i}$。

我们仿照克鲁斯卡尔的加边顺序，在合并联通块的同时转移这个 dp，转移形如 $g'_{k}=\min_{i+j=k}\max \{g_i,g_j,w\}$，然后置 $g_0=g_{sz}=0$。显而易见这是对的。复杂度同树上背包，为 $\mathcal{O}(n^2)$。

不过由于我们可以很显然的发现 $g_i,g_j$ 在非端点处总是大于等于 $w$，所以其实存在一些办法做到 $\mathcal{O}(\frac{n^2}{w})$，具体怎么做咕咕咕，有兴趣的可以问一下 gpt。