本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-15 10:29:24

:::::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)\lpha(n)\log V)$，其中 $V$ 是边权值域，空间复杂度为 $\Theta(n+m)$。

code