题解：P9531 [JOISC 2022] 复兴计划

· · 题解

将 y=|x-w_i| 的图像画出来，会形如以 (w_i,0) 为定点的一个斜率为 1 的倒 V 型，并且容易发现 y=|x-w_i| 与 y=|x-w_j| 只会有一个交点。大胆猜测对于原图每条边，以这条边作为最小生成树的 x 形成一个连续区间。

考虑如何说明这件事。对于一个 x，|x-w_i| 的最小生成树可以看作两棵最小生成树合并：

  1. 对于 w_i<x，w_i 的最大生成树
  2. 对于 w_i\ge x，w_i 的最小生成树

因此，一个直观的感受是 |x-w_i| 的最小生成树的 w_i 会在值域上呈连续的一段。将 w_i 按从小到大排序扫一遍，设当前扫到 i，我们从 i-1 开始倒着枚举并查集维护加边直到和 (u_i,v_i,w_i) 这条边形成环，令加边后出现环的这条边为 w_j，即这个环内的最小边权。实际考虑一个前缀的最小生成树是必然会从这个环中断边，对 x 的取值进行分讨：

若 x<w_j，则 w_{j},w_{j+1},\dots,w_{i-1} 比 w_i 更优，因为这部分比 x 大所以做的是最小生成树，按照 kruskal 的加边顺序到 w_i 会成环所以死掉了。

若 x>w_i，则 w_{j+1},w_{j+2},\dots,w_i 比 w_j 更优，因为这部分比 x 小所以做的是最大生成树，按照 kruskal 的加边顺序到 w_j 会成环所以死掉了。

若 x\in [w_j,w_i]，考虑什么时候 w_i 能比 w_j 更优，即 w_i-x<x-w_j，解得 x>\frac{w_i+w_j}{2}，因此若 x\in [w_j,\frac{w_i+w_j}{2}] 则按照加边顺序最大生成树至少会加到 w_j，而最小生成树部分若加到 w_i 则合并时会形成环而 |w_j-x|<|w_i-x| 因此 w_i 死掉了；否则相反，在 x>\frac{w_i+w_j}{2} 时 w_i 会替代掉 w_j，w_j 对答案的贡献终止，w_i 对答案的贡献开始。

通过这个方法可以找出对于每条边 w_i 其贡献区间 [l_i,r_i] 代表若 x\in [l_i,r_i] 则 w_i 会在 |x-w_i| 的最小生成树中。这个构造同时也证明了贡献形成连续一段的正确性。问题转换成 \sum\limits_{x\in [l_i,r_i]}|x-w_i|，还是把绝对值拆开，对 w_i 的贡献分讨：

显然 x=w_i 时 w_i 会被贡献，于是 l_i\le w_i\le r_i，这个拆区间是不重不漏的。将答案写成 kx+b 的形式，接下来直接维护两个差分数组 k,b，分别区间加即可。询问时由于保证 x 单增，可以维护一个单调的指针往右移，加上指针位置差分数组的贡献即可。这里值域会很大，可以离散化或者直接 map。

复杂度为 O(nm+q\log m)。说明一下为什么第一部分不是 O(m^2)，注意到每次那个出现环的位置 j 的移动量与当前生成森林大小变化量同级，因此均摊下来每次只需枚举 n 个位置就可以找到环。