题意
给定无向带权连通图，每条边是黑色或白色，求恰好有 $need$ 条白边的生成树最小权。
$n = 5 \times 10^4, m = 10^5$
题解
二分一个 $k$，把所有白边的权值都加上 $k$，以达到调整最小生成树的白边数量。
注意有个坑，因为有边权相等的情况，所以跑生成树是有可能取不到刚好 $need$ 的。
代码
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n = bin, m = bin, need = bin, temp;
vector<vector<tuple<tp, tp, tp>>> e(n);
for (tp i = 0; i < m; ++i) {
tp s, t, c, l; bin >> s >> t >> c >> l;
e[s].emplace_back(t, c, !l);
}
tp l = -200, r = 200;
auto check = [&]() -> tp {
vector<tuple<tp, tp, tp, tp>> g;
for (tp i = 0; i < n; ++i) {
for (auto& [t, c, l] : e[i]) g.emplace_back(i, t, c, l);
}
stable_sort(FULL(g), [](const auto& a, const auto& b) { return make_pair(get<2>(a), get<3>(a)) < make_pair(get<2>(b), get<3>(b)); });
lib::DSU d(n);
temp = 0;
tp white = 0;
for (tp i = 0, cnt = -1; i < m && cnt != n; ++i) {
if (d.root(get<0>(g[i])) != d.root(get<1>(g[i]))) {
temp += get<2>(g[i]);
d.link(get<0>(g[i]), get<1>(g[i]));
++cnt;
white += get<3>(g[i]);
}
}
return white;
};
while (l <= r) {
tp mid = (l + r) / 2;
for (auto& p : e) {
for (auto& [t, c, l] : p) c += l * mid;
}
if (check() <= need) r = mid - 1;
else l = mid + 1;
for (auto& p : e) {
for (auto& [t, c, l] : p) c -= l * mid;
}
}
for (auto& p : e) {
for (auto& [t, c, _l] : p) c += _l * l;
}
check();
bin << temp - need * l << '\n';
}
void MIST() {
}