口胡。
problem
一个图，边带权，有 \(k\leq 50\) 个关键边，对于 \(0\leq i\leq k\) 求出恰好含有 \(i\) 条关键边的最小生成树的权值和。\(n\leq 10000,m\leq 10^6,k\leq 50\)。
solution
WQS 二分。
考虑记 \(f_x\) 表示 \(i=x\) 的答案。在平面上描出 \((i,f_x)\) 这些点，我们用一个 dfs 发现这些点是一个下凸包。
（证明：考虑不管限制跑最小生成树会用到 \(t\) 个关键边，那么 \(x\leq t\) 肯定单调不增，\(x\geq t\) 肯定单调不减（好吧是错的））
用一条斜率为 \(k\) 的直线去切这个凸包，假设切到 \(x\)，那么写出这条直线是：\(f_x=kx+b\to b=f_x-kx\)。
由于这个 \(b\) 是最小的（不然就不叫切），我们可以认为我们是将所有关键边的权值加上 \(-k\) 之后的最小生成树，拿到了 \(x\) 条边。
随着斜率的增加，\(x\) 也在增加。
因此我们二分斜率 \(k\)，使所有关键边的权值减去 \(k\) 跑最小生成树，得到 \(x\)，根据 \(x\) 决定 \(k\) 往哪一边跑。
细节：
- 一上来就考虑 \(i=0\)，将没有用的非关键边扔掉。因为随着 \(i\) 的增加，后面的边也绝不可能用到。
- 如果关键边自己搞出来环，不管它，等到后面加到不能再加，就把这些边按边权大小一个一个加上去。