问题抽象

我们有一个连通无向图，$N$ 个节点，$M$ 条边，每条边 $i$ 有宽度 $W_i$。

对于每个查询 $X_j$，我们需要选择一些边构成生成树，使得整张图连通，并且最小化总代价：

$$\sum_{e \in \text{生成树}} |W_e - X_j|$$

其中我们可以任意调整边的宽度（每调整 $1$ 花费 $1$），但宽度不能低于 $1$。

---

关键观察

1. 问题转化

实际上，我们不需要真的"调整所有边的宽度"，而是选择一组边构成生成树，使得这些边宽度与 $X_j$ 的绝对差之和最小。

因为对于不在生成树中的边，我们可以不管它们（不花费代价），只需要保证生成树中的边连通全图即可。

2. 按边权排序

将边按宽度 $W_i$ 排序。对于固定的 $X$，考虑每条边的代价函数 $f_e(X) = |W_e - X|$。

这是一个分段线性函数：当 $X \le W_e$ 时，代价为 $W_e - X$；当 $X \ge W_e$ 时，代价为 $X - W_e$。

3. 生成树的结构

对于固定的 $X$，我们想要选择生成树使得 $\sum |W_e - X|$ 最小。

这等价于：我们偏好选择宽度接近 $X$ 的边。

实际上，最优生成树可以通过以下方式获得：

• 将边按 $|W_e - X|$ 排序
• 用 Kruskal 算法选择前 $N-1$ 条边（按这个排序）

但直接对每个 $X_j$ 做一次 Kruskal 是 $O(QM \log M)$，不可行。

---

核心解法

1. 区间划分

注意到当 $X$ 变化时，边的相对顺序只在某些关键点发生变化。这些关键点就是所有 $(W_i + W_j)/2$（其中 $i \ne j$）。

实际上，我们只需要考虑所有 $W_i$ 以及它们的中点，因为 $|W_e - X|$ 的排序只在 $X$ 跨越这些点时改变。

2. 双序列维护

将边按 $W_i$ 排序得到序列 $w_1 \le w_2 \le \cdots \le w_M$。

对于给定的 $X$，代价函数 $|w_i - X|$ 在 $i \le k$ 时是递减的（$X - w_i$），在 $i > k$ 时是递增的（$w_i - X$），其中 $k$ 是满足 $w_k \le X$ 的最大下标。

因此，按 $|w_i - X|$ 排序等价于：

• 将 $w_1, \dots, w_k$ 按降序排列（因为 $X - w_i$ 随 $i$ 增大而减小）
• 将 $w_{k+1}, \dots, w_M$ 按升序排列
• 然后归并这两个序列

3. 生成树选择的单调性

关键结论：存在一个下标 $p(X)$，使得最优生成树由：

• 最小的 $r$ 条边（按原 $W_i$ 排序）中的某些边
• 和最大的 $s$ 条边中的某些边组成 其中 $r + s = N-1$。

更精确地，最优生成树会选择最接近 $X$ 的 $N-1$ 条边（按 $|W_i - X|$ 排序）。

4. 预处理所有关键区间

由于 $N \le 500$，但 $M$ 可能很大，$Q$ 非常大，我们需要高效处理。

解法思路：

1. 将数轴按所有 $W_i$ 和 $(W_i + W_j)/2$ 分成 $O(M^2)$ 个区间
2. 在每个区间内，最优生成树的边集不变（按 $|W_e - X|$ 的排序不变）
3. 对每个区间，计算生成树代价关于 $X$ 的线性函数
4. 对于查询 $X_j$，找到所在区间，用对应的线性函数计算答案

由于 $M \le 10^5$，$O(M^2)$ 太大，需要优化。实际上，只需要考虑 $O(MN)$ 个关键点，因为生成树最多 $N-1$ 条边。

---

算法框架

1. 排序边：将边按 $W_i$ 排序
2. 生成关键点：考虑所有 $W_i$ 以及它们的中点，但只保留可能改变生成树组成的点
3. 区间处理：对每个区间 $[L,R]$，确定最优生成树的边集，并计算代价函数 $cost(X) = \sum_{e \in T} |W_e - X|$
4. 查询处理：对每个 $X_j$，二分找到所在区间，用对应的线性函数计算答案

---

复杂度优化

• 关键点数量：$O(MN)$
• 每个区间用 Kruskal 求生成树：$O(M \log M)$
• 总预处理：$O(M^2N \log M)$ 仍然太大

实际高效做法：

• 利用最优生成树在 $X$ 变化时的单调性
• 使用双指针维护当前最优生成树
• 预处理所有"边交换"事件，当 $X$ 变化时只需 $O(1)$ 更新生成树

---

总结

这道题的核心是：

1. 问题转化：将重构问题转化为生成树选择问题
2. 代价函数分析：$|W_e - X|$ 是分段线性函数
3. 区间划分：最优生成树在 $X$ 的某些区间内保持不变
4. 高效查询：预处理线性函数，支持快速查询

这是一道结合了生成树理论、参数化优化和分段函数分析的高难度题目，需要深入理解图论性质和函数性质才能设计出高效算法。