传送门
思路： p r u f e r 序 列 prufer序列 prufer序列板子题。
显然有公式： ( n − 2 ) ! ∑ i = 1 n ( d e g r e e [ i ] − 1 ) ! \dfrac{(n-2)!}{\sum\limits_{i=1}^n(degree[i]-1)!} i=1∑n(degree[i]−1)!(n−2)!
因为此题数据范围较大，可能会爆 l o n g l o n g long\ long long long，但是题目保证答案不会超过 L L LL LL,所以我们考虑转化为乘法做。
显然上述公式等价于从 n − 2 n-2 n−2个数，分别选出 d [ 1 ] − 1 d[1]-1 d[1]−1个位置放1， d [ 2 ] − 2 d[2]-2 d[2]−2个位置放 2 2 2， … , d [ n ] − 1 \dots,d[n]-1 …,d[n]−1个位置放 n n n，所以前提是必须满足 ∑ i = 1 n ( d e g r e e [ i ] − 1 ) = n − 2 \sum\limits_{i=1}^n(degree[i]-1)=n-2 i=1∑n(degree[i]−1)=n−2
所以每次我们相当于从剩下的数选出 d [ i ] − 1 d[i]-1 d[i]−1个数，即为 C ( n − 2 − s u m , d [ i ] − 1 ) C(n-2-sum,d[i]-1) C(n−2−sum,d[i]−1)。
第一次： C ( n − 2 , d [ 1 ] − 1 ) C(n-2,d[1]-1) C(n−2,d[1]−1)
第二次: C ( n − 2 − ( d [ 1 ] − 1 ) , d [ 2 ] − 1 ) C(n-2-(d[1]-1),d[2]-1) C(n−2−(d[1]−1),d[2]−1)
第三次： C ( n − 2 − ( d [ 1 ] − 1 ) − ( d [ 2 ] − 1 ) , d [ 3 ] − 1 ) C(n-2-(d[1]-1)-(d[2]-1),d[3]-1) C(n−2−(d[1]−1)−(d[2]−1),d[3]−1)。
依次类推，再根据乘法原理即可算出答案，这样巧妙避免除法爆 L L LL LL.
此外此题需要注意， n = 1 n=1 n=1需要特判，因为公式是从 n − 2 n-2 n−2计算的，还需对度数为0点的特判，显然存在这样的孤点，不可能构成树。
当 n = = 1 时 n==1时 n==1时，如果 d [ 1 ] = = 0 d[1]==0 d[1]==0显然只有唯一解，否则无解，因为孤点不可能有度数。
时间复杂度： O ( n 2 ) O(n^2) O(n2)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=150+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second ll c[N][N],d[N],sum,ans=1; void fun(int n){ for(int i=0;i<=n;i++) c[i][i]=c[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } int main(){ int n,ok=1; scanf("%d",&n); if(n==1){ //特判n=1的情况. scanf("%d",&d[1]); puts(d[1]?"0":"1"); return 0; } for(int i=1;i<=n;i++){ scanf("%lld",&d[i]),d[i]--,sum+=d[i]; if(d[i]==-1) ok=0; } if(sum!=n-2||!ok) return puts("0"),0; fun(n),sum=0; for(int i=1;i<=n;i++) ans*=c[n-2-sum][d[i]],sum+=d[i]; printf("%lld\n",ans); return 0; }