:::::info[题目基本信息]
考察：WQS 二分，生成树（提高+/省选-）。
题目简介：
给定一个有 n 个点 m 条边的无向带权图，每条边要么是白色要么是黑色，求需要有 k 条白边前提下的最小生成树总边权，保证有解。
数据范围：
1\le n\le 5\times 10^4
1\le m\le 10^5
0\le k<n
对于图上所有边，边权不超过 100。
时间限制：2s。
空间限制：500MB。
:::::
先介绍下 WQS 二分。
:::::success[WQS 二分详解]
设有一凸函数为 f(x)，它表示一问题在某一条件为 x 时价值或代价为 f(x)，现在我们要求 f(k)。
这类问题一般满足：函数 f(x) 在 D（D 为定义域）上的最小值好求，同时也好知道该最小值在何处，但 f(x) 在 x 固定时的值不好求，这时我们考虑把 f(x) 转化为整个函数的最小值。
我们钦定 f(x) 为下凸函数，上凸函数同理。画出随便一个 f(x) 的图像：
现在我们要求 C 点通过线性变换转化为整个函数的最小值，由于这是一个凸函数，我们想到用一条直线去切这个函数，就像这样：
这样从函数上的点到直线上的铅垂线的长度变为了变换后函数的值，容易发现此时 C 点成为了函数最小值，这样就可以计算 C 点值了。
实际问题中我们可以二分直线斜率使得快速找到这条切线的斜率，从而得到答案。
:::::
在这道题中，注意到不限制条件时的最小生成树容易得出，所以我们考虑套用 WQS 二分。设 f(p) 为有 p 条白边时的最小生成树总边权，现在我们只需要证明 f(p) 是凸函数，首先我们感性理解下觉得更有可能是下凸函数，因为最小生成树一般不会全是白边或全是黑边。
下面套用下 oi-wiki 的证明：
:::::success[证明]
首先转化一下原问题，由于该函数的定义域为 [0,n-1]\cap\mathbb Z，所以证明该函数为下凸函数等价于证明 \forall i\in(0,n-1)\cap\mathbb Z,f(i)\le\dfrac{f(i-1)+f(i+1)}{2}。
不妨钦定图上所有边权均不同，对于有相同的情况，选一个趋近于 0 的正实数 eps，令这些边加上或减去若干个 eps 就转化为了边权均不同的情况，通过极限可以证明边权有相同的情况。
小结论：设同一个图上存在两棵不同的生成树 S 和 T，那么有 \forall e\in S,\exist f\in T，使得 S 和 T 交换 e 和 f 后的两个图 S' 和 T' 仍是生成树。
::::success[证明]
设 e=(u,v)，S 删除 e 后 u 和 v 断开，由于 T 加上 e 后存在一个环，所以在 T 中可以找到一条在 u 到 v 路径上的一条边，选取任意一条为 f，那么容易证明 T' 是一棵生成树。
对于 S' 考虑反证法，删除 e 后的 S 变成了有两个联通分量的森林，如果没有一个 T 图中在 u 到 v 路径上的 f 使得 S' 是生成树，那么所有的 f 的相连的两个点在 S 中都在一个联通分量里，但是由于 u 和 v 在 S 中在两个连通分量里，那么所有的 f 在 T 中也无法连接 u 和 v，与假设矛盾，故 S' 是一棵生成树。
证毕。
::::
设 S 是一棵有 i+1 个白边的最小生成树，T 是一棵有 i-1 个白边的最小生成树，选择一条在 S 中但不在 T 中的白边 e，总有一条在 f 中的白边 f 满足交换这两边后 S' 和 T' 还是生成树，对于 f 分类讨论：
当 f 是一条既在 S 中又在 T 中的边，那么由于 e 不在 T 中，所以 e\ne f，所以 S' 中会出现两条 f，故该情况不存在，f 不存在于 S 中。
当 f 是一条白边时，则 S' 仍是有 i+1 个白边的生成树，T' 仍是有 i-1 个白边的生成树，由于它们的总边权和仍是 f(i-1)+f(i+1)，所以他们均是最小生成树，可以得到两边边权相同，与大前提矛盾，故该情况不存在，f 是黑边。
当 f 是存在于 T 中但不存在于 S 中的一条黑边时，S' 和 T' 都是有 i 条白边的生成树，由于它们的总边权和仍是 f(i-1)+f(i+1)，容易得到 f(i)\le\dfrac{f(i-1)+f(i+1)}{2}。
证毕。
:::::
为了实现减去直线的操作，我们可以给每条白边的边权减去二分的直线斜率，直接对于每条直线斜率跑一遍 Kruskal 即可，当跑出来的最小生成树白边数量最大值不小于 k 时减小直线斜率，否则增大直线斜率。
一个小优化是容易发现白边和黑边分别保持有序，所以在开始我们将两种边分别排序，跑 Kruskal 时跑一轮归并就可以了。
时间复杂度为 \Theta(m\log m+(n+m)\alpha(n)\log V)，其中 V 是边权值域，空间复杂度为 \Theta(n+m)。