题解 P2290 【[HNOI2004]树的计数】

· · 题解

在博客查看

大致题意： 给定每个点的度数，让你求有多少种符合条件的无根树。

前言：prufer序列

简介

据$hl666$大佬说，一切与度数有关的树上计数问题，都可以用它以及它的性质来解决。 而听说$ZJOI$最近特别喜欢出计数题，所以有必要学一学。 #### 转化$1$：从无根树到$prefur$序列 现在，给你一棵树，我们要考虑如何把它变成$prefur$序列。 ![](https://cdn.luogu.com.cn/upload/pic/54939.png) 我们需要重复进行以下操作，直至树中只剩下两个点： - 找到一个**度数为$1$**，且**编号最小**的点。（其中编号最小保证了后面将会提到的$prufer$序列的唯一对应性，同时也方便从$prufer$序列转化回无根树） - 把这个点的父亲节点加入序列，然后把这个点从树中删除。 然后我们就得到了一个长度为$n-2$的序列，这就是$prufer$序列。 所以它有什么实际意义呢？ ~~我也不知道。~~ 以上面的图为例，我们可以模拟这一过程如下： - 找到$4$号节点，将其父结点加入序列，然后将其删去。此时序列：$\{2\}$。 - 找到$5$号节点，将其父结点加入序列，然后将其删去。此时序列：$\{2,3\}$。 - 找到$3$号节点，将其父结点加入序列，然后将其删去。此时序列：$\{2,3,1\}$。 - 找到$6$号节点，将其父结点加入序列，然后将其删去。此时序列：$\{2,3,1,2\}$。 - 找到$2$号节点，将其父结点加入序列，然后将其删去。此时序列：$\{2,3,1,2,1\}$。 所以，最后得到的$prufer$序列就是$\{2,3,1,2,1\}$。 #### 转化$2$：从$prufer$序列到无根树 还是以刚才那棵树为例吧，我们要考虑如何把它的$prefur$序列变回它本身。 我们需要重复进行以下操作，直至点集中只剩下两个点：（初始化所有点都在点集中） - 取出$prufer$序列最前面的元素$x$。 - 取出**在点集中**的、且**当前**不在$prufer$序列中的最小元素$y$。（这恰好呼应了前面提到过的选取编号最小的节点） - 在$x,y$之间连接一条边。（注意前面的取出相当于删除） 最后，我们在点集中剩下的两个点中连一条边。 显然这有$n-1$条边，且绝对不会形成环，因此它是一棵树，且就是原树。 以上面的序列为例，我们可以模拟这一过程如下： - 取出$2,4$连边。此时$prufer$序列：$\{3,1,2,1\}$，点集：$\{1,2,3,5,6,7\}$。 - 取出$3,5$连边。此时$prufer$序列：$\{1,2,1\}$，点集：$\{1,2,3,6,7\}$。 - 取出$1,3$连边。此时$prufer$序列：$\{2,1\}$，点集：$\{1,2,6,7\}$。 - 取出$2,6$连边。此时$prufer$序列：$\{1\}$，点集：$\{1,2,7\}$。 - 取出$1,2$连边。此时$prufer$序列：$\{\}$，点集：$\{1,7\}$。 最后再在$1,7$间连边，就可以得到原树了。 #### $prufer$序列的性质及相关结论 讲了这么多，我们最关键的还是$prufer$序列的一些性质，以及与其有关的一些结论。（~~毕竟前面也提到过，我也不知道这东西有什么实际意义~~） - **重要性质：$prufer$序列与无根树一一对应。** 这应该显然吧，通过前面的介绍应该可以直接得出。 而由这个性质，我们才能推导出后面的结论。 - **度数为$d_i$的节点会在$prufer$序列中出现$d_i-1$次**。 当某个节点度数为$1$时，会直接被删掉，否则每少掉一个相邻的节点，它就会在序列中出现$1$次。 因此共出现$d_i-1$次。 - **一个$n$个节点的完全图的生成树个数为$n^{n-2}$。** 对于一个$n$个点的无根树，它的$prufer$序列长为$n-2$，而每个位置有$n$种可能性，因此可能的$prufer$序列有$n^{n-2}$种。 又由于$prufer$序列与无根树一一对应，因此生成树个数应与$prufer$序列种树相同，即$n^{n-2}$。 - **对于给定度数为$d_{1\sim n}$的一棵无根树共有$\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$种情况**。 由上面的性质可以知道，度数为$d_i$的节点会在$prufer$序列中出现$d_i-1$次。 则就是要求出$d_i-1$个$i(1\le i\le n)$的全排列个数。 而上面那个式子就是可重全排列公式。（即**全排列个数**除以**重复元素内部的全排列个数**） 大致就是这些。 ### 解法 现在回到这道题，这显然是一道利用$prufer$序列求解的裸题。 考虑到由$prufer$序列得到的结论：**对于给定度数为$d_{1\sim n}$的一棵无根树共有$\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$种情况**。 套公式即可。 ### 高精/质因数分解/$Python

等等，答案小于10^{17}？

这看似在long\ long范围内，但是我们前面有除法啊！运算过程中肯定会爆long\ long！

然后就有3种做法：

我自然是选择了Python。

最后提醒一句，需要判无解！

代码

n=(int)(input())#读入n
if n==1:#特判n=1的情况
    x=(int)(input());#读入唯一的节点度数
    if x==0:print(1);#如果这个节点度数为0，说明只有一种解法
    else:print(0);#否则，无解
    exit();#退出程序
f=[0 for i in range(n+5)];f[0]=1;#建立阶乘数组
for i in range(1,n+1):f[i]=f[i-1]*i;#预处理阶乘
ans=f[n-2];tot=0;s=input().split();#初始化ans为(n-2)!，用tot统计度数和来判断是否无解
for i in range(n):
    x=(int)(s[i]);
    if x==0:print(0);exit();#如果存在某个点度数为0，说明图不连通，输出0
    tot+=x-1;ans//=f[x-1];#统计度数和，更新答案
if(tot==n-2):print(ans);#如果度数和为n-2，输出ans
else:print(0);#否则无解