树的计数（prufer序列 或 purfer序列）

题解

首先我们要知道一条性质，prufer序列中的某个点出现次数为该点在树中度数-1

感性理解一下，其实按照prufer序列求法自己推一下就出来了

设题目里给的度为$d[]$

先将所有的d--

然后按照排列组合得出来

这是多重集排列数

首先从n中选择d[1]个数是$C_{n}^{d[1]}$然后再从剩余n-d[1]中选d[2] $C_{n-d[1]}^{d[2]}$依次类推

$C_{n}^{d[1]}\times C_{n-d[1]}^{d[2]}\times C_{n-d[1]-d[2]}^{d[3]}\times ……\times C_{n-d[1]-……-d[n-1]}^{d[n]}$

得到

$\frac{n!}{\sum\limits_{i=1}^{n}d[i]!}$

高精转移就完了

还是过不了？

一些特判：

首先该题会有无解的情况

然后当只有一个点时方案数为1

然后当出现度数为0的点时方案数要特殊处理

树的计数（prufer序列 或 purfer序列）

原文：https://www.cnblogs.com/znsbc-13/p/11222262.html