题解：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|$ 的最小生成树可以看作两棵最小生成树合并：

因此，一个直观的感受是 $|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$ 个位置就可以找到环。