[洛谷 2290][HNOI2004]树的计数

题目链接

https://www.luogu.org/problem/P2290

题解

在解决本题之前，我们需要认识一下 prufer 序列。

prufer 序列可以将一个含有 \(n\) 个节点的无根树转化为一个长度为 \(n-2\) 的序列。

构建 prufer 序列的过程很简单：我们每次选出所有度为 \(1\) 的节点中编号最小的点，将它删除，并将其父亲节点加入 prufer 序列，重复上面的操作直到树中只剩下两个节点为止。

我们可以发现，无根树和 prufer 序列是一一对应的。

同时我们还会发现一个显然的结论，无根树中度数为 \(d\) 的点会在 prufer 序列中出现 \(d-1\) 次（度数为 \(1\) 的节点会被直接删除，否则会先删除与其相邻的 \(d-1\) 个点，即将该点加入 prufer 序列 \(d-1\) 次）。

有了上面这个结论，就可以来解决本题了。

求无根树的数量，等价于求满足条件的 prufer 序列的数量。容易发现我们事实上是在求一个可重集的排列数目，将上面的结论带入可重集排列公式，就可以得到答案了。

$$\frac{(n-2)!}{\prod_{i=1}^n d_i-1}$$

虽然答案保证在 long long 范围内，但要注意中间结果溢出的问题。

（python 大法好啊）

n=int(input())
s=input().split()
if n==1 :
    if int(s[0])==0 :
        print(1)
    else :
        print(0)
else :
    f=[1]
    for i in range(1,n+1):
        f.append(f[i-1]*i)
    ans=f[n-2]
    cnt=0
    for i in range(n):
        cnt=cnt+int(s[i])
        ans=ans//f[int(s[i])-1]
    if cnt!=2*n-2 :
        print(0)
    else :
        print(ans)