T5 可恶の施工：最小生成树、贪心
题意简化
给定一个无向带权连通图，求在保证图连通的前提下，最少删除多少条边使得剩余边的总权值不超过给定的限制 ppp。若无法满足条件，输出 -1。
关键观察
* 最优解的结构一定是 保留权值较小的边，同时保证图的连通性。
* 这与 最小生成树 (MST) 的性质一致：MST 是权值和最小的连通子图。
* 因此，问题转化为：在 MST 的基础上，尽可能多地保留权值小的额外边，使得总权值不超过 ppp。
算法思路
1. 构建最小生成树：
* 使用 Kruskal 算法求出 MST，记录其权值和 sumMSTsum_{\text{MST}}sumMST 和使用的边数 n−1n-1n−1。
* 若 sumMST>psum_{\text{MST}} > psumMST >p，直接输出 -1（无解）。
2. 贪心添加额外边：
* 将 非 MST 边 按权值从小到大排序。
* 依次尝试添加这些边，直到总权值超过 ppp。
* 最终删除的边数为 总边数 mmm - 保留的边数。
时间复杂度分析
* Kruskal 算法：排序边 O(mlogm)O(m \log m)O(mlogm)，并查集操作 O(mα(n))O(m \alpha(n))O(mα(n))，总体 O(mlogm)O(m \log m)O(mlogm)。
* 贪心添加额外边：遍历至多 mmm 条边，O(m)O(m)O(m)。
* 总复杂度：O(T⋅mlogm)O(T \cdot m \log m)O(T⋅mlogm)，其中 TTT 为测试用例数量。
部分分策略
测试点 数据范围 特殊性质 可用算法 预计得分 1-2 N,M≤10N, M \leq 10N,M≤10 无 暴力枚举删边组合 10pts 3-4 N,M≤100N, M \leq 100N,M≤100 无 枚举保留边数 + Kruskal 30pts 5 N≤105,M≤2e5N \leq 10^5, M \leq 2e5N≤105,M≤2e5 所有边权相等 贪心保留最多边 25pts 6 M=N−1M = N-1M=N−1（树结构） 树边权和是否超过 ppp 直接判断 sum≤psum \leq psum≤p 10pts 7-10 N≤105,M≤2e5N \leq 10^5, M
\leq 2e5N≤105,M≤2e5 无 正解算法 100pts
特殊性质说明：
* 性质 A：所有边权相等时，保留尽可能多的边即可，无需考虑权值大小。
* 性质 B：图为树时，若 sumMST>psum_{\text{MST}} > psumMST >p 则无解，否则必须保留全部树边（不能删除任何边，否则不连通）。
正解代码
