题解 连通图计数

· · 题解

考虑 m=n-1 的时候，唯一可能的无向连通图就是一棵树，同样删掉 i 之后的连通块数量恰好就是 i 的度数，所以给出的 a_i 也就是 i 的度数，用 Prüfer 序列可知答案就是 \binom{n-2}{a_1-1,a_2-1,\dots,a_n-1}。

考虑 m>n-1 的时候，将无向连通图建成圆方树，那么容易发现 a_i 表示的就是 i 这个圆点连接的方点数量。

当 m=n 的时候，只有恰好一个方点连接的圆点数量超过 2，并且它连接的圆点数量我们是可以计算出来的，恰好为 2n-\sum a_i，所以我们把这个方点加入再使用 Prüfer 序列求对应的树的数量，然后再乘以 (2n-\sum a_i-1)!/2 作为环上排列的顺序。

当 m=n+1 的时候，有两种情况，一种情况是只有一个方点连接的圆点数量超过 2，另一种情况是有两个这样的方点。如果只有一个方点，同样这个方点连接的圆点数量恰好是 2n-\sum a_i，使用上面相同的方法求出树的数量，然后再乘以 2n-\sum a_i 个点 2n-\sum a_i+1 条边的点双数量；如果有两个方点，则这两个方点的度数之和为固定的，那么就枚举其中一个方点的度数，增加两个方点求一下对应的树的数量，不过需要注意两个方点不能直接连接，这种情况需要减去，并且最后还需要记得除以 2，因为两个方点本质相同。

考虑如何求 n 个点 n+1 条边的点双数量，注意到这样的点双中应该恰好有两个点度数为 3，其余点度数都为 2，那么实际上就是两个点由三条没有标号的链连接起来，并且这三条链没有顺序，且最多只有一条链长度为 0。于是我们得到这样的点双数量为 \binom{n}{2}\frac{(n-2)!(\binom{n}{2}-3)}{3!}。