Description

　　自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在

任意两点间连线,可产生多少棵度数满足要求的树?

Input

　　第一行为N(0 < N < = 1000),

接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

　　一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

3

1

-1

-1

Sample Output

2

HINT

　　两棵树分别为1-2-3;1-3-2

该题运用到了树的prufer编码的性质：

  (1)树的prufer编码的实现

        不断 删除树中度数为1的最小序号的点，并输出与其相连的节点的序号  直至树中只有两个节点

  (2)通过观察我们可以发现

        任意一棵n节点的树都可唯一的用长度为n-2的prufer编码表示

        度数为m的节点的序号在prufer编码中出现的次数为m-1

  (3)怎样将prufer编码还原为一棵树？？

        从prufer编码的最前端开始扫描节点，设该节点序号为 u ,寻找不在prufer编码的最小序号且没有被标记的节点 v ，连接   u,v,并标记v，将u从prufer编码中删除。扫描下一节点。

该题需要将树转化为prufer编码

因为一个点度为di，那么在prufer序列中出现di-1次

所以对于已知的度，sum=∑di-1(已知)，cnt为有多少已知点

那么从序列中选出sum为方案C(sum,n-2)

对于已知di，产生的方案数为${

{(n-2)!} \over {\prod (d_i - 1)}}$

对于无限制的点，可以这样考虑，剩下的n-2-sum为每一位选择都有n-cnt种

所以方案为(n-cnt)^n-2-sum

把三者乘起来

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 struct Big_Num  8 {  9   int a[5005],len; 10   Big_Num() 11   {} 12   Big_Num &operator *=(const int &b) 13   {
    int i; 14     for (i=1;i<=len;i++) 15       a[i]*=b; 16     for (i=1;i<=len;i++) 17       a[i+1]+=a[i]/10,a[i]%=10; 18     int loc=len+1; 19     while (a[loc]) 20       { 21     a[loc+1]+=a[loc]/10; 22     a[loc]%=10; 23     loc++; 24       } 25     len=loc-1; 26   } 27   void print() 28   {
    int i; 29     for (i=len;i>=1;i--) printf("%d",a[i]); 30     cout<
           
            >n; 40 flag=0; 41 for (i=1;i<=n;i++) 42 { 43 scanf("%d",&d[i]); 44 if (d[i]!=-1) cnt++,sum+=d[i]-1; 45 if (d[i]==0||d[i]==n) flag=1; 46 } 47 if (n==1) 48 { 49 cout<<1; 50 return 0; 51 } 52 if (n==2) 53 { 54 if ((d[1]==0||d[1]>1)||(d[2]==0||d[2]>1)) 55 cout<<0; 56 else cout<<1; 57 return 0; 58 } 59 if (sum>n-2) 60 { 61 cout<<0; 62 return 0; 63 } 64 if (flag) 65 { 66 cout<<0; 67 return 0; 68 } 69 for (i=2;i<=n-2;i++) 70 du[i]++; 71 for (i=2;i<=n-2-sum;i++) 72 du[i]--; 73 for (i=1;i<=n;i++) 74 if (d[i]!=-1) 75 { 76 for (j=2;j<=d[i]-1;j++) 77 du[j]--; 78 } 79 for (i=1;i<=n-2-sum;i++) 80 du[n-cnt]++; 81 82 for (i=2;i<=2000;i++) 83 { 84 if (vis[i]==0) 85 { 86 pri[++tot]=i; 87 pre[i]=i; 88 } 89 for (j=1;j<=tot;j++) 90 { 91 if (pri[j]*i>2000) break; 92 vis[i*pri[j]]=1; 93 pre[i*pri[j]]=pri[j]; 94 if (i%pri[j]==0) break; 95 } 96 } 97 for (i=2000;i>=2;i--) 98 if (pre[i]!=i) 99 {100 du[pre[i]]+=du[i];101 du[i/pre[i]]+=du[i];102 du[i]=0;103 }104 ans.a[1]=1;ans.len=1;105 for (i=2;i<=2000;i++)106 if (du[i]>0)107 {108 for (j=1;j<=du[i];j++)109 ans*=i;110 }111 ans.print();112 }