[洛谷 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)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注