Description
一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，编程需要输出满足d(vi)=di的树的个数。
Input
第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。
Output
输出满足条件的树有多少棵。
Sample Input
2 1 2 1
Sample Output
题解
$Prüfer$编码&$Cayley$公式。
预备知识：->戳我<-
这里谈下自己的理解：
（此段与题目无关，可选择跳过）首先对于$Cayley$公式，其实讲的就是“$n$阶完全图生成数个数为$n^{n-2}$”，换言之就是“$n$个带编号顶点的无根生成树共$n^{n-2}$个”。
证明：这里引用$Prüfer$编码，不了解的话可以戳上文链接。其实就是对于任何一棵无根生成树，都有一个长度为$n-2$的序列。这个序列是这样定义的：每次在叶节点中找到一个编号最小的节点，将其删去，记录下相邻节点。因为是无根，若顶点只有$2$个，显然只有一棵树，长度就是$n-2$。
而对于任何一个$Prüfer$编码都能够还原成一棵无根树。
我们回到这道题，我们拥有这样一个结论：“任何一个$Prüfer$编码都能够还原成一棵无根树”。
那么我们就可以用$Prüfer$编码来解决问题。
我们发现第$i$个点会在$Prüfer$编码中出现$d[i]-1$次：因为自己“被删”需要$1$个度，他的其他相邻节点“被删”要$d[i]-1$个度。
那么等于说$i$这个数会在编码中出现$d[i]-1$次。
因为数列长度为$n-2$，我们看有序排列：总共有$(n-2)!$个
考虑去重：因为此时$Prüfer$编码中的数字$i$恰好出现$d[i]-1$次我们只需要对于每个$i$都除以$(d[i]-1)!$就可以了。
所以答案就是。
注意要特殊讨论构成不了树的情况。
//It is made by Awson on 2017.10.6
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define sqr(x) ((x)*(x))
using namespace std;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
} int n, a[];
int cnt[];
int pre[]; void prepare() {
bool isprime[];
int q[], top = ;
memset(isprime, , sizeof (isprime));
isprime[] = ;
for (int i = ; i <= n; i++) {
if (isprime[i]) q[++top] = i;
for (int j = ; j <= top && i*q[j] <= n; j++) {
pre[i*q[j]] = q[j];
isprime[i*q[j]] = ;
if (i%q[j] == ) break;
}
}
}
void noanswer() {
printf("0\n");
exit();
}
void work() {
read(n);
prepare();
int sum = ;
for (int i = ; i <= n; i++) {
read(a[i]);
if (!a[i] && n != ) noanswer();
a[i]--; sum += a[i];
}
if (sum != n-) noanswer();
for (int i = ; i <= n-; i++) {
int j = i;
while (pre[j]) {
cnt[pre[j]]++;
j /= pre[j];
}
cnt[j]++;
}
for (int i = ; i <= n; i++)
for (int j = ; j <= a[i]; j++) {
int k = j;
while (pre[k]) {
cnt[pre[k]]--;
k /= pre[k];
}
cnt[k]--;
}
LL ans = ;
for (int i = ; i <= n; i++)
for (int j = ; j <= cnt[i]; j++)
ans *= i;
printf("%lld\n", ans);
}
int main() {
work();
return ;
}