自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:49:18，当前版本为作者最后更新于2023-08-03 23:40:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 $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!}$。