刚考完以为是神仙题……后来发现好像挺蠢的…… QwQ
给你一张 \(n\) 个点 \(m\) 条边的无向图（不一定连通），有 \(q\) 组询问，每组询问给你 \(2\) 个正整数 \(l,h\)，你需要选出一些边，满足边权都在 \([l,r]\) 范围内，连通尽量多的点对，在此基础上使得边权和最小。
\(n,m,q\le 10^5,\space w_i\le 10^4\)（原题 \(n\le 1000,\space q\le 10^6\)）
动态最小生成树（汗）
我怎么什么都没写过
考场上花 10 分钟写了 5 分 \(O(qn)\) 暴力就滚了
假设这题可以离线，先将所有边按权值从大到小排序。
依次判断每条边的两端点是否连通，若未连通则连上（这样连通的点对数必定增多），若连通则替换掉一条树上这两点之间的简单路径上 权值最大的一条边（\(\text{cut}\) 一下权值最大的那条边，\(\text{link}\) 一下这条边）。
加边的同时动态处理询问。对于一组询问 \([L,R]\)，若当前插入的边的权值是 \(\ge L\) 的最小值，则我们决定处理这组询问。此时最小生成（森林）上的所有边权都 \(\ge L\)，我们直接扔掉所有权值 \(\gt R\) 的边，剩余的边的权值和就是答案。发现边权很小，所以可以用树状数组动态维护最小生成（森林）中权值为 \(i\) 的边数，单点修改，区间查询。
考虑在线，我想这题时居然忘了加边和询问是分开的了……
依然把边按权值从大到小排序，依次加入最小生成（森林），然后在主席树的第 \(w_i\) 个版本上单点修改即可，在线处理询问 \([L,R]\) 时在主席树的第 \(L\) 个版本上区间查询即可。
复杂度 \(O(n\log n)\)。
仔细想想好像确实挺水的，所以还是我太菜了
原文：https://www.cnblogs.com/scx2015noip-as-php/p/bzoj4046.html