CF1515F Phoenix and Earthquake

题意：大地震把 个城市之间的全部 条道路震垮了。现在，需要紧急恢复 条原来的道路，使得任意两个城市可以互相到达。

每个城市分别存有 吨沥青。修复一条道路需要 吨沥青，如果两个城市 之间有一条损坏的道路，且两个城市的沥青总量 ，那么就可以消耗这两个城市的 吨沥青来修路。

修好了路之后，装载沥青的卡车就可以在路上跑，在这一部分连通的城市中任意地来往运送沥青了。

判定能否让 个城市连通，如果能，输出任意一种修路的方案。

，时间 。

---

首先，若沥青总和不足 ，则显然无法完成。

• 猜想：一旦沥青总数 （称作性质A）就一定能完成。

  证明：只需证明图为树的情况，一般图的条件显然比树容易有解。

  修路 可以视作将两端的点 缩合为一个点，且新点权值 。

  不难发现，在若干缩合操作后，性质A仍然保持，于是考虑归纳。只需证对于任意满足性质的树，都至少能修出一条路。

  反证，若对于任意边 都有 ，对于边 ，将限制扩大为 。特殊地，任选一条 ，限制写为 。

  这样，我们把 个点的权值（不重不漏地）划分到 个不等式里面去了，且不等式右侧总和为 ，这就能得到点权和 ，矛盾。证毕。

---

接下来考虑如何快速求出一种方案。

对于一般图，我们可以任保留一棵生成树，忽略其他的边，这样可以简化问题。

根据如上证明，一种正确策略是：每次修任意一条能修的边。但这样不好维护。

我们考虑将策略特化以便维护。

• 策略一

  （根据[NOI2020] 制作菜品）考虑权值最大的点 和权值最小的点 ，有 。

  证明 ：若不满足，则说明 ，和最大的情况是除了最小值外都是 ，仅为 ，不足 ，矛盾。

  也就是说，最大点 任意连边都是合法的。

  实现时，用堆维护目前的权值最大点，并查集启发式合并维护边表即可。

• 策略二

  考虑任意一个叶子 ，若 ，直接连边 。

  否则必有 ，则将点 忽略，剩余的点形成（必然有解的）子问题。处理完剩余的点之后再连接 （不难发现此时必然能连）。

  实现时，在树上 dfs ，当点 的子树访问完毕准备弹栈时：

  • 若 （要考虑子树内连边的影响），则连边 ，令 。

  • 若 ，则将边 加入一个栈中。

  在 dfs 完毕后，弹出栈中的边，并依次连接。

注意到上述两种策略都能导出对应的归纳证明，而且证明是构造性的，而非上文中的反证法。启发：找策略时可以尝试从构造性证明入手。