题目大意

给定 $N$ 个节点（建筑）和 $M$ 条带权边（管道），其中前 $N-1$ 条边构成初始生成树。每条边有月维护费 $C_i$，可以花费一天时间替换一条边（关闭一条现有边并激活一条新边）。还有一个推进器可以将一条边的费用降低 $D$（但不能低于 $0$）。

要求计算：最少需要多少天，可以得到一棵包含节点 $1$ 的最小生成树（总费用最小）。

算法思路

核心思想

Kruskal 算法 + 替换边分析，考虑推进器对边权的影响。

关键观察

推进器只能用于一条边，因此最优策略是把它用在新加入的边中权值最大的那条上

最终的最小生成树可能与初始生成树不同，需要替换一些边

每次替换操作（一天）可以替换一条边

算法步骤

1. 预处理边权

标记初始的 $N-1$ 条边（old = 1）

对推进器处理：实际上在排序时考虑推进器效果，即最终可能用 $max(0, C_i - D)$ 作为比较

2. Kruskal 求最小生成树

按边权排序，权值相同时优先选初始边（避免不必要的替换）

构建最小生成树，统计需要替换的边数（即非初始边的数量）

3. 特殊处理推进器

如果最后加入的边权值 $\ge D$，推进器可以直接用在这条边上

否则，需要额外考虑是否能用一条初始边替换当前边，从而节省一天操作

算法流程

读入数据并标记初始边

按边权排序（考虑推进器效果）

运行 Kruskal 算法：

记录使用的非初始边数量 ans

记录最后加入的边权 Mx

判断推进器使用：

如果 Mx >= D，直接输出 ans

否则，尝试用一条初始边替换，减少一天操作

复杂度分析

时间复杂度：$O(M \log M)$，主要来自排序

空间复杂度：$O(N + M)$，存储并查集和边集

总结

本题是最小生成树问题的变种，主要考察：

Kruskal算法应用：标准MST算法基础上考虑边替换

推进器策略：只能用于一条边的特殊约束处理

替换操作计数：通过标记初始边统计需要的最小操作天数

边界情况处理：推进器效果与边权大小的关系

该解法通过巧妙的排序策略（权值相同时优先初始边）和推进器使用分析，在 $O(M \log M)$ 时间内解决了最优替换问题，体现了在经典算法基础上处理特殊约束的思维能力。