题目大意：给定一个 $n$ 行 $m+1$ 列的格点图。其中，第 $i$ 列与第 $i+1$ 列之间的连边方式、边权，和第 $1$ 列与第 $2$ 列之间完全一样。对于每一个 $k \in [1, m]$，求出只保留前 $k$ 层（即前 $k+1$ 列点）时，这张图的最小生成树权值和。
$n,m\le 10^5$，第 $1$ 列与第 $2$ 列之间有 $\le 2\times 10^5$ 个边，边权最大为 $30$。
我们保留所有 $w\le 1$ 的边，然后算出形成的连通块数量，假设是 $x$；然后保留所有 $w\le 2$ 的边，算出形成的连通块数量 $y$，显然 $w=2$ 的边加入了 $x-y$ 条；然后保留所有 $w\le 3$ 的边，算出形成的连通块数量 $z$，显然 $w=3$ 的边加入了 $y-z$ 条……以此类推，我们可以算出所有种边权的边的加入条数，从而算出答案。因为边权最大为 $30$，所以时间复杂度是正确的。而算法的正确性可以类比 Kruskal 的算法过程进行证明。
我们现在将问题弱化为了给定一些没有边权的边，求格点图的连通块数量。因为题目要求求出所有 $k$ 的答案，不难想到去增量计算（求出每增加一列之后的答案）。
假如现在先算第一层（第一列和第二列）的答案，根据 Kruskal 算法的过程，我们最开始有一个边的集合 $E$（因为没有边权，所以无需排序）。这个集合中包括了第一层的所有边（更具体地，一条从第一列 $u$ 连到第二列 $v+n$ 的边在 $E$ 中表示为 $(u,v+n)$）。然后使用一个大小为 $2n$ 的并查集维护前两列的点的连通性。其中 $1\sim n$ 代表第一列的点，$n+1\sim 2n$ 代表第二列的点。跑 Kruskal 就可以计算出连通块数量了（连通块数量为总点数减去在 Kruskal 算法过程中成功合并的边数）。
如果我们要算前两层的答案，实际上加入的边还是那些边，不同的是第二列的点已经初始具有一些连通性了。
我们将第一列与第二列的连通性情况“压扁”，意思就是说假如第二列有两个点 $u+n,v+n$ 因为第一列的连边情况而在同一个连通块中，那么就当作存在一条 $u$ 与 $v$ 相连（注意这里不加 $n$）的虚边加入到 $E$ 中。此时使用一个大小为 $2n$ 的并查集维护二三列的点的连通性。其中 $1\sim n$ 代表第二列的点，$n+1\sim 2n$ 代表第三列的点，类比之前的算法就可以算出答案了：清空并查集，先继承第一层的答案，然后将 $E$ 中的所有虚边都合并了（注意虚边的合并不会对答案产生贡献，只是为了初始化并查集），然后将 $E$ 中的非虚边都合并了（如果两侧不联通，就会对答案产生 $+1$ 的贡献）。
后面的每层做法都是类似的。之后我们将 $1\sim n$ 代表的列称为左列，$n+1\sim 2n$ 代表的列称为右列。
实际上我们可以更大胆，因为不存在边权，所以枚举 $E$ 的顺序实际上是可以随意的。所以继承上一层的答案后，我们可以先将 $E$ 中的非虚边都合并了（如果两侧不联通，就会对答案产生 $+1$ 的贡献）。然后再枚举虚边合并，如果虚边两侧已经联通，那么说明形成了一个环，只需要在环上删除恰好一条边即可，那么答案 $-1$。
因为每次都会继承上一层的答案，我们可以维护答案的差分数组。
我们每次都要重新枚举 $E$，然后重新算并查集，显然并不优。再次应用 $E$ 的顺序是可以随意的性质，我们按照一条边加入 $E$ 的先后去枚举 $E$，相当于每次并查集不清空，先继承上一层答案的差分值，只考虑相较上次新加入 $E$ 的那些虚边，在并查集上继续进行合并即可，如果加入的虚边两侧已经联通，那么差分值会 $-1$。
此时我们还需要判断合并两个点之后，是否会造成右列中两个连通块合并，从而形成新的虚边。这里就需要维护每个连通块中是否存在右列的点（$>n$ 的点），如果是，随意取出一个就好（可以维护连通块中编号最大的点，每次判断这个点是否 $>n$ 即可）。
因为最多会加 $O(n)$ 条虚边（最多合并 $O(n)$ 次），所以均摊之后复杂度就是 $O(n\alpha(n)w)$。
