不久前写的kruskal（以及prim 最小生成树总结（很轻微，不会还是建议更系统性地学
那么今天就是kruskal重构树了
主要是最近想起了一道题
总之就是维护静态种类数的一个东东
身为一只（咿吱）观察力敏锐的小鸽子，我们会发现对于同一起点，要求越低越好（可以走更多的路，也就可以走到更多的地点，相应的答案也就只增不降）
卧槽，离线+排序+暴力啊，也就是伪 n^2 的做法
这么说，是我赢了？
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
nooooooo
所以怎么办呢
深入观察一下
我们会发现当两个点（下文中以 u,v 相称）至低能以 x 的代价联通时
对于任意 k > x ， 询问“u,k” 和“v,k”得到的答案是一样的
毕竟是双向边，当他们可以互相到达的时候，其实你可以理解为可以用tarjan缩点在一起了（感性理解
我们又会发现，两个点之间的这个 x 是固定的
我们双会发现，两个点之间的路径是唯一（因为会先做一遍生成树）且最极端（大或小）的
我们最终叕会发现，两个点之间的路径就正好对应这个 x
于是我们诞生了一个做法——
分为 n 个不同阶段，分别表示与 ？个点处于同一并查集时的答案
两点之间由 x 为权值连边，再做最小生成树……
blah blah 我草这啥啊，鉴定为口胡，要么就是很难实现的东西
不过这72个字对我们的思路有一点作用
带入情境，我们发现可能的答案最多只有2n个（我去，我也直到现在才想到）
因为任意两个点的可达子集是必定完全包含或完全不包含的
这个是非常容易证的
假设在两个可能不同的限制（ s_1=s_2,w_1>w_2 ）下，两个可达集合 S_1,S_2 ，存在不完全包含关系，那么也就是说在更紧的限制下，有可能会比宽松的限制多走一条边，那么也就是说这条边的长度要满足 w_2≥ l ≥w_1,但是又因为 w_1>w_2 ，所以不可能
诶，那么怎么表示这 2n 个答案（实际上是 2n-1 的）之间的关系呢（也就对应的是包含或不包含）
所以直接讲正解吧——kruskal重构树
因为我们发现当两个点集对应的边集的权值大小存在明显的大小关系时（假设这个点集满足上面的限制）
那么我们知道了这两个点集对应答案之间要么完全不包含，要么就是大包小
那么实际就是这样：
要么被他人阻断了链接
要么在满足更高的条件下一定满足低的条件，即完全包含
真正的正解部分
如何维护答案之间的关系呢
生成树呗
但是答案显然是不行的
因为我们发现，做普通的生成树就注定会有父子关系
而从父节点开始，是否能回到儿子节点又成为了一个问题，那此时答案又该如何预处理呢
我们在一个点，又如何管理与其相连的所有边呢？（指一个点有很多儿子节点，但是边的大小有别，此时儿子节点就算能到达父节点，也未必能去兄弟节点）
如此，最右边的就是kruskal重构树
这东西我认为是极为巧妙的
它把边弄成了点做最小生成树
也就是说，这个点对应一个 x
那么原来的点单独构成的点集也就对应着哪儿都去不了的答案
完美地表示了 2x-1 个最大可达集合
这里题目的代码就不放了，放kruskal重构树的
for(int i = 1;i <= m;i++)
{
if(find(e[i].u)!=find(e[i].v))
{
int x = find(e[i].u),y = find(e[i].v);//为了表示点集之间的大小关系，因此需要找到点集中的祖先
v[++cnt] = e[i].w;//新建节点，记录权值
f[x] = f[y] = f[cnt] = cnt;//更新父节点
}
}
