看到这些\(n^{2}\)的并查集，且每次并查集都是连续的，那么我们就可以利用倍增进行并查集（类似st表，贡献可重复问题）。然后我们可以将所有并查集都加进去后在进行下传。比如在P3295中，我们需要算出最后有多少个连通块，那么我们如果[i][k]和[j][k]在一个连通块里，那么[i+(1<<(k-1))][k-1]和[j+(1<<(k-1))][k-1]在一个连通块里，[i][k-1]和[j][k-1]在一个连通块里然后不断下传就可以了。然后对于xj的这题来说，要求的是最小生成树，那么如果当前的两个在同一连通块，就不用下传了。不一样的话，那就下传到最底部，并且加上权值。这个的时间复杂度是有保证的，因为你每次传下去都会连边，每次都会将一些并到同一个集合里面，这个操作不会超过O(n log n)次
标签：连通,P3295,查集,炸弹,xyd,蹦蹦 From： https://www.cnblogs.com/wuhupai/p/18311412