某谷 Rated 比赛泛做

P9535 「YsOI2023」连通图计数

非常好题目，爱来自湖南。

\(m=n-1\) 等价于给定度数求树的个数，这是一个经典题，在「HNOI2004」树的计数有描述，即利用 Prufer 序列得到答案为 \(\binom{n-2}{(d_1-1)(d_2-1)\ldots(d_n-1)}\)。

\(m=n\) 即基环树，对于整个大环建立一个虚点，该点向环上的所有点连边，环上的点均不连边，则该图变成一棵树，这棵树所有点的点度同样已经确定，可以直接做，最后再乘上环上点的排列顺序。

注意到建立虚点的过程等价于圆方树中方点的建立，也就是说，该题的基本思路是转成圆方树后计数。

\(m=n+1\)，分两种情况讨论：

• 仙人掌：即两个环并不相交，此时同样建立圆方树，则两方点的度数之和可以得知，暴力枚举一边的度数即可知道所有点的度数，从而套用 \(m=n-1\)，需要减去两个方点相连的情况，此时只需要将两个点绑成一个点，同样跑 \(m=n-1\) 但乘上 \(2\) 的该点度数的若干次方即可，因为两方点本质不同，所以还要除以二。
• 一个大的点双，同样建立圆方树，跑一遍 \(m=n-1\) 的情况后剩下的就是计算 \(n\) 个点 \(n+1\) 条边的点双个数，注意到此时的点双一定会有两个度数为 \(3\) 的点，去掉这两个点剩下三条链且至多一条长度为 \(0\)，可以计算得出答案为 \(\binom{n}{2}\frac{(n-2)!(binom{n}{2}-3)}{3!}\)。

总时间复杂度 \(O(n)\)。