自从明明学了树的结构,就对奇怪的树产生了兴趣…… 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
一个整数,表示不同的满足要求的树的个数,无解输出0
3 1 -1 -1
2
两棵树分别为1-2-3;1-3-2
这道题用了一个叫做prufer编码的东西（新技能get）
首先prufer编码是啥呢？ 引用一下怡红公子的话：
该题运用到了树的prufer编码的性质： (1)树的prufer编码的实现 不断 删除树中度数为1的最小序号的点，并输出与其相连的节点的序号 直至树中只有两个节点 (2)通过观察我们可以发现 任意一棵n节点的树都可唯一的用长度为n-2的prufer编码表示 度数为m的节点的序号在prufer编码中出现的次数为m-1 (3)怎样将prufer编码还原为一棵树？？ 从prufer编码的最前端开始扫描节点，设该节点序号为 u ,寻找不在prufer编码的最小序号且没有被标记的节点 v ，连接 u,v,并标记v，将u从prufer编码中删除。扫描下一节点。
这个东西自己画一下挺好理解的。
感觉它最神奇的一点就是这n-2位的编码可以随便填，没有特殊的限制，一个编码就能对应一棵树 一开始我想的是现在n个点中选一个点当根，然后剩余n-1个点都选一个自己的父节点，根据度数判断这个点是多少个点的父节点，但这样有一些问题，比如可能出现环。 而prufer编码就不会出现这样的问题了。
如果我们知道了每个点的度数d[i] 那么满足的树的个数（即prufer编码个数）为 \(\frac{(n-2)!}{\prod(d[i]-1)!}\) 但是题目中有一些点的度数是不知道的。设知道度数的点有m个，它们的 \(\sum d[i]-1\) 为s 那么满足的树的个数为 $ \frac{s!}{\prod(d[i]-1)!} \times C_{n-2}^s \times (n-m)^{n-2-s} \ =\frac{(n-2)!}{\prod(d[i]-1)! \times (n-2-s)!} \times (n-m)^{n-2-s} $ 注意要高精度
另一种高精度写法（本质无区别，只是几个月后的写法） 【捂脸】
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1005; int n,d[N]; struct Bign{ int s[3*N],l; Bign() { memset(s,0,sizeof(s)); l=0; } }ans; Bign mul(Bign a,int x){ Bign c; for(int i=0,g=0;;i++){ if(i>=a.l && g==0) { c.l=i; break; } c.s[i]=(a.s[i]*x+g)%10; g=(a.s[i]*x+g)/10; } return c; } Bign div(Bign a,int x){ Bign c; c.l=a.l; for(int i=a.l-1,g=0;i>=0;i--){ g=g*10+a.s[i]; c.s[i]=g/x; g=g%x; } while(c.l && c.s[c.l-1]==0) c.l--; return c; } void output(Bign a){ for(int i=a.l-1;i>=0;i--) printf("%d",a.s[i]); printf("\n"); } int main() { int m,t=0; scanf("%d",&n); m=n-2; for(int i=1;i<=n;i++) { scanf("%d",&d[i]); if(d[i]==-1) t++; else m-=(d[i]-1); } ans.s[ans.l++]=1; for(int i=m+1;i<=n-2;i++) ans=mul(ans,i); for(int i=1;i<=n;i++) for(int j=2;j<d[i];j++) ans=div(ans,j); for(int i=1;i<=m;i++) ans=mul(ans,t); output(ans); return 0; }转载于:https://www.cnblogs.com/lindalee/p/9031970.html
相关资源：数据结构—成绩单生成器