根号分治做法
我太菜了，只会库鲁斯卡尔算最小生成树，库鲁斯卡尔需要对边排序，通过人类的智慧，我们发现每个询问用到的边应该不会太多，我们分两种情况。
也不能叫根号分治吧，定义 为分治边界。
点数大于分治边界的查询在整个边集则在全边集中找有用边跑库鲁斯卡尔，否则两两枚举找有用边。
经过计算 时理论时间复杂度最优（复杂度一个是
，一个是
），但因为奇妙的常数原因好像并不是这样的。
我们找到了这一次有用边组成的边集后进行排序，排序后无脑跑库鲁斯卡尔就行，我的并查集甚至只用了一个路径压缩优化。（是的，我知道你会惊讶地说：“这都能过？！”）
京公网安备 11010502036488号