Kruskal 及重构树的应用
考虑一个图的边权进行某种限制，可以将边权按顺序考虑，抠出最小生成树进行处理。
考虑边权的最大生成树上走一定最优，毋庸置疑。能化简的东西尽快化简
考虑 kruskal 算法中，合并两棵子树 \(v_1,v_2\) 的情况。
我们发现如果从正在合并的这条边的左右窜来窜去不划算，因为中间这条边限制最严，不如先去一个子树完成任务，然后润过去。
以先做 \(v_1\) 为例，假设子树 \(v_2\) 的答案为 \(s_2\)，两棵子树的任务价值总和分别为 \(x_1,x_2\)，合并后答案为 \(S\)，合并的边权为 \(w\) 那么：
- \(S+x_1 \le w\)，你做完了 \(v_1\) 首先要通过合并的边。
- \(S+x_1 \le S_2\)，你还要能完成 \(v_2\) 子树才行。
我们发现 (1) 条件很严，足以走完 \(v_1\) 子树。
那么合并答案就好了。
首先限制条件用最小生成树没问题。但是答案应该考虑哪个？
其实整个水槽高度齐平然后被外围墙挡住这个事情不自然，我们就假设所有水位要低于当前墙的最大高度
那么合并就考虑墙两边的连通块，每一边都有“依赖这堵墙水位齐平”的贡献。很好算的。
杂题
我是脑瘫。
直接放缩条件，一条边不算边权，一条边双倍边权即可。多记录 2 个状态，表示是否使用了不算边权/双倍边权的技能（雾）
很简单的最短路题
标签：化简,图论,子树,边权,合并,答案,考虑 From： https://www.cnblogs.com/BreakPlus/p/17533492.html