题面：
一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，你的程序需要输出满足d(vi)=di的树的个数。
题解：
乍一看是组合数学，，，当然了，实际上也是组合数。
只不过要是知道prufer数列就很简单了。
那先来看看prufer数列吧！
同时，prufer数列还支持再转化为树：
设{a1,a2,..an-2}为一棵有n个节点的树的Prufer序列，另建一个集合G含有元素{1..n}，找出集合中最小的未在Prufer序列中出现过的数，将该点与Prufer序列中首项连一条边，并将该点和Prufer序列首项删除，重复操作n-2次，将集合中剩余的两个点之间连边即可。 ------------------------------摘自百度百科
这里我们可以观察到，树和prufer数列是一一对应的关系，也就是说一棵树的prufer数列是唯一确定的，同理，一个prufer数列对应的树也是唯一确定的，
这就非常妙妙了。
我们通过观察将树转化为prufer数列的方法可以得知，一个点在prufer数列中出现的次数实际上就是一个点的入度-1，
也就是说这道题实际上是：
给定prufer数列的限制条件，求树的种数
然后我们又知道树和prufer数列是一一对应的，所以题面就变成了：
给定prufer数列中各个点的出现次数，求prufer数列不重复的全排列
那做法就很清晰了
因为prufer数列的长度是n-2,(看上面的转换方法很容易发现）
所以全排列是(n-2)!,但是由于有重复出现的点，因此这些排列中会有很多重复的，
有哪些重复呢？
稍微了解一点组合数相关知识就知道了，
假设点i出现了x次，那么对于任意一次排列，这x个相同的点都有x!种排列方式，
因此一种排列就会因为点i而被多计算x!次，其他也是一样的，
所以总的公式就是
(n-2)!/(s[1]! * s[2]!.....)
其中s[i]表示点i在prufer数列中的出现次数（也就是入度-1）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 170 5 #define LL long long 6 int n,all; 7 int s[AC]; 8 LL ans; 9 /*prufer序列emmmm，，， 10 貌似说的还是比较有道理的？ 11 任意prufer序列可以对应唯一确定的树，所以可以求prufer序列的不重复的全排列 12 通过求prufer序列的过程可以感知到，，，一个点在prufer序列中的出现次数，应当是其度数-1 13 因此这里给出了度数，也就相当于给出了prufer序列，那么对其求不重复的全排列即可 14 15 一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。 16 上面这句话比较重要。通过上面的定理， 17 1）我们可以直接推出n个点的无向完全图的生成树的计数：n^(n-2) 即n个点的有标号无根树的计数。 18 2）一个有趣的推广是，n个节点的度依次为D1, D2, …, Dn的无根树共有 (n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ] 个， 19 因为此时Prüfer编码中的数字i恰好出现Di-1次。 20 即 n种元素，共n-2个，其中第i种元素有Di-1个，求排列数。 21 3）n个节点的度依次为D1, D2, …, Dn，令有m个节点度数未知，求有多少种生成树？(BZOJ1005 明明的烦恼) 22 令每个已知度数的节点的度数为di，有n个节点，m个节点未知度数，left=(n-2)-(d1-1)-(d2-1)-...-(dk-1) 23 已知度数的节点可能的组合方式如下 24 (n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left! 25 剩余left个位置由未知度数的节点随意填补，方案数为m^left 26 于是最后有 27 ans=(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left! * m^left 28 by https://www.cnblogs.com/dirge/p/5503289.html */ 29 int read() 30 { 31 int x=0;char c=getchar(); 32 while(c > '9' || c < '0') c=getchar(); 33 while(c >= '0' && c <= '9') x=x*10 + c - '0',c=getchar(); 34 return x; 35 } 36 37 void pre() 38 { 39 n=read(); 40 for(R i=1;i<=n;i++) 41 { 42 s[i]=read() - 1 , all+=s[i] + 1; 43 if(s[i] < 0 && n != 1)//error!!! 如果只有一个节点的话是可以允许没有边的 44 {//但也要注意将边都集中在某几个点上以至于后面的点不合法的情况 45 printf("0 "); 46 exit(0); 47 } 48 } 49 if(all != 2 * n - 2)//如果是不合法数据就直接退了 50 { 51 printf("0 "); 52 exit(0); 53 } 54 } 55 56 void work() 57 { 58 ans=1; 59 for(R i=n-2; i>0 ;i--)//也许从高处开始乘会减少爆的可能性？毕竟除也是从高处开始的 60 { 61 ans *= i; 62 for(R j=1;j<=n;j++)//防爆措施 63 { 64 if(s[j] <= 1) continue; 65 while(!(ans % s[j])) 66 { 67 ans/=s[j],--s[j]; 68 if(s[j] == 1) break; 69 } 70 } 71 } 72 printf("%lld ",ans); 73 } 74 75 int main() 76 { 77 // freopen("in.in","r",stdin); 78 pre(); 79 work(); 80 // fclose(stdin); 81 return 0; 82 }