比较自然的做法。

对于两条边权相同的边，不妨钦定编号较小的边更小。

有结论：对于任意一条边，使得它在最小生成树中出现的 $x$ 是一个连续区间。

:::info[证明]

考察最小生成树经典结论：一条边 $e$ 不被包含在最小生成树中，当且仅当存在一个包含 $e$ 的环，使得 $e$ 的边权大于环上其他边的边权。

考虑对于一条边 $f$，何时 $|w_e-x|>|w_f-x|$。设 $m=\dfrac{w_e+w_f}{2}$，若 $w_e<w_f$，则要有 $x>m$，否则要有 $x<m$。

考察一个包含 $e$ 的环 $C$ 使得 $e$ 的边权大于环上其他边的边权。观察到 $w_e<w_f$ 时 $m>\dfrac{w_e}{2}$，$w_e>w_f$ 时 $m<\dfrac{w_e}{2}$，因此 $C\setminus \{e\}$ 中不能同时存在 $<w_e$ 和 $>w_e$ 的边。若其他边都 $<w_e$，则 $x>\max\limits_{f\in C\setminus \{e\}}\dfrac{w_e+w_f}{2}$；若其他边都 $>w_e$，则 $x<\min\limits_{f\in C\setminus \{e\}}\dfrac{w_e+w_f}{2}$。而最终 $x$ 的取值范围是这些限制的并集，必然形如 $x<L\lor x>R$，因此 $e$ 能被包含在最小生成树中时，$x$ 的取值范围就是 $[L,R]$。$\Box$

:::

考虑直接分治，将所有询问排序，分治到区间 $[L,R]$ 表示考虑到 $x_L\leq x\leq x_R$。我们对 $x=x_{mid}$ 跑一次最小生成树，那么对于不在生成树上的边，直接看其边权 $w$ 和 $x_{mid}$ 的大小关系即可判断要扔到左区间还是右区间。而对于生成树上的边，其可以同时扔到左区间和右区间。最后递归到叶子节点时统计答案。显然复杂度烂完了，还不如直接暴力。

考虑一个优化：分治到 $[L,R]$ 时，对 $x=x_L$ 和 $x=x_R$ 分别跑最小生成树，那么考察所有同时在两个生成树上的边，我们可以确定这些边的 $x$ 的取值区间包含 $[L,R]$，此时不必再把这些边扔到左右两边递归，可以直接贡献到答案上。注意到贡献形式为对于每个 $L\leq i\leq R$，令 $ans_i\gets |w-x_i|$，那么找到一个分界点使得前面的 $x_i<w$，后面的 $x_i\geq w$，两部分都是加上关于 $x_i$ 的一次函数的形式，直接维护 $k,b$ 的差分即可。同时，我们要把这些边两端的点用并查集缩起来，给点重新编号之后再递归到两侧。

注意到这样优化之后，这个分治结构和线段树基本一致，每条边只会被插入 $\mathcal{O}(\log{q})$ 个区间内，因此时间复杂度为 $\mathcal{O}(m\log{q}\log{m}+q\log{q})$。

跑得挺快。

:::success[主要代码]

void solve(int l, int r, int n, vector<Edge> &edges) {
	if (l > r || edges.empty()) return;
	auto kruskal = [&](int X) {
		vector<Edge> E; E.reserve(n - 1);
		stable_sort(edges.begin(), edges.end(), [&](const Edge &lhs, const Edge &rhs) {
			int wl = abs(lhs.w - X), wr = abs(rhs.w - X);
			return wl != wr ? wl < wr : lhs.id < rhs.id;
		});
		dsu.init(n);
		for (int i = 0; i < edges.size(); ++i) {
			auto [id, u, v, w] = edges[i];
			u = dsu.find(u), v = dsu.find(v);
			if (u == v) continue;
			dsu.unite(u, v);
			E.push_back(edges[i]);
			if (E.size() == n - 1) break;
		}
		return E;
	};
	auto Tl = kruskal(qr[l]), Tr = kruskal(qr[r]);
	static bool visl[M], visr[M], vism[M];
	for (auto e : Tl) visl[e.id] = 1;
	for (auto e : Tr) visr[e.id] = 1;
	dsu.init(n);
	for (auto [id, u, v, w] : edges) if (visl[id] && visr[id]) {
		dsu.unite(u, v);
		int p = lower_bound(qr + l, qr + r + 1, w) - qr;
		--k[l], ++k[p], b[l] += w, b[p] -= w;
		++k[p], --k[r + 1], b[p] -= w, b[r + 1] += w;
	}
	static int mp[N];
	int tot = 0;
	for (int i = 1; i <= n; ++i) if (dsu.find(i) == i) mp[i] = ++tot;
	for (int i = 1; i <= n; ++i) mp[i] = mp[dsu.find(i)];
	vector<Edge> E;
	for (auto [id, u, v, w] : edges) {
		if (visl[id] && visr[id]) continue;
		u = mp[u], v = mp[v];
		if (u != v) E.push_back({id, u, v, w});
	}
	edges = move(E), n = tot;
	for (auto e : Tl) visl[e.id] = 0;
	for (auto e : Tr) visr[e.id] = 0;
	if (l == r) return;
	int mid = l + r >> 1;
	auto T = kruskal(qr[mid]);
	for (auto e : T) vism[e.id] = 1;
	vector<Edge> El, Er;
	for (int i = 0; i < edges.size(); ++i) {
		if (vism[edges[i].id]) El.push_back(edges[i]), Er.push_back(edges[i]);
		else (edges[i].w <= qr[mid] ? El : Er).push_back(edges[i]);
	}
	for (auto e : T) vism[e.id] = 0;
	solve(l, mid, n, El), solve(mid + 1, r, n, Er);
}

:::