[Prufer 序列 & 计数 & 图论] CodeForces 156D Clues
https://www.luogu.com.cn/problem/CF156D
题意
给定一张 \(n\) 个点 \(m\) 条边的带标号无向图，设有 \(c\) 个连通块，求添加 \(c - 1\) 条边使得形成一棵树的方案数，并对 \(p\) 取模。
\(1 \leq n \leq 10^5, 0 \leq m \leq 10^5, 1 \leq p \leq 10^9\)。
题解
因为大小为 \(c\) 的树与长度为 \(c - 2\) 的 Prufer 序列是 双射 关系，所以我们可以对 Prufer 序列进行计数。
我们可以把这 \(c\) 个连通块都看成一个点来计算，设第 \(i\) 个连通块在最后的生成树中的度数为 \(d_i\)，根据父亲序列转 Prufer 序列的过程，容易发现最后剩下的一条边一定连接根节点和它的其中一个子节点，所以分两种情况讨论：
-
\(i\) 不是根节点，\(i\) 与其子节点的连边都会被删掉，所以 \(i\) 在 Prufer 序列中出现了 \(d_i - 1\) 次。
-
\(i\) 是根节点，因为最后将剩下一条连接根节点和它的其中一个子节点的边，所以\(i\) 在 Prufer 序列中也出现了 \(d_i - 1\) 次。
然后我们就可以确定 Prufer 序列的数量了，即：
然后我们开始确定每一个连通块是哪一个点往外连了边，直接乘法原理即可，方案数：
其中 \(siz_i\) 表示第 \(i\) 个连通块的大小。
整理一下，若这 \(c\) 个连通块在生成树中对应的度数为 \(d_1, d_2, \dots, d_c\)，则方案数为：
然后我们就要枚举 \(d\) 数组了，先放上来式子：
很好，这是一个十分丑陋的式子，但是我们有 多项式定理：
所以显然，$$\sum_{d_1 + d_2 + \dots + d_c = 2c - 2}\dbinom{c - 2}{d_1 - 1, d_2 - 1, \dots, d_c - 1}\prod_{i = 1}^{c}siz_i ^ {d_i - 1} = (siz_1 + siz_2 + \dots + siz_c) ^ {c - 2} = n^{c - 2}$$
所以答案为 \(\displaystyle n^{c - 2} \times \prod_{i = 1}^{c}siz_i\)。
非常好的一道计数题，结合了 Prufer 序列 + 多项式定理。