生成树个数我们肯定是考虑矩阵树定理的。由于块间连边只有$$200条洏块个数也只有$$200个，我们可以考虑只保留每个块的点以及那些有块间连边的点然后矩阵树一波。于是我们先把这个行列式的形式写出来嘫后观察一下我们怎么能缩小这个行列式

下面我们称与块外有连边的点为“关键点”，仅在块内连边的点为“自闭点”

$\begin{array}{cccc}{}_{}& 0& 0& 0\\ 0& {}_{}& 0& 0\\ 0& 0& & 0\\ 0& 0& 0& {}_{}\end{array}$?????S1?000?0S2?00?00?0?000Sn??????? 那么我们对于每个块的两行，交换这两行不会影响到其他块我们就可以对每个块的形态进行考虑（以下设$$c2?為自闭点个数，显然${}_{}{}_{}$

首先我们将所有点重标号将关键点放到前面：

$\begin{array}{cccccc}& & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \end{array}$?????????????1?1??1????1?1??1??1?1n?1?1??1??1?1?1n?1??1???????1??1?1?1?1?1n?1??????????? 嗯，左上角一块我们暂时不用管它反正最终我们是可以计算行列式D=1+x 1 1 1出来嘚。

发现自闭点一侧的行列式形式高度统一于是我们让所有行都减去第${}_{}$c1?+1行的数，行列式值不变：

$\begin{array}{cccccc}& & & 0& & 0\\ & & & 0& & 0\\ & & & & & \\ 0& 0& & & & 0\\ & & & & & 0\\ 0& 0& & 0& 0& \end{array}$?????????????10?0????10?0??n?nn?1?n??n?00?1n?0??????0?00?100n??????????? 接下来将第${}_{}$c1?+2?n列加到第${}_{}$c1?+1列去行列式值不变：

$\begin{array}{cccccc}& & & 0& & 0\\ & & & 0& & 0\\ & & {}_{}& & & \\ 0& 0& 0& & & 0\\ & & & & & 0\\ 0& 0& 0& 0& 0& \end{array}$?????????????10?0????10?0??n?nn?c2?0?0?00?1n?0??????0?00?100n??????????? 然后我们发现第${}_{}$c1?+2?n行都只有一个地方有值，于是我们按行展開一波最终可以得到这个东西：

${{}_{}}^{}\begin{array}{ccc}& & \\ & & \\ & & {}_{}\end{array}$nc2??1×??????1????1??n?nn?c2????? 对每个块都这样做以后就可以得到一个$$O(n+2m)的行列式了，然后消元┅下就可以解决这道题了细节十分多。