Description
自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?
Input
第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output
一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input
3
1
-1
-1
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
把三者乘起来
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Big_Num
{
int a[],len;
Big_Num()
{}
Big_Num &operator *=(const int &b)
{int i;
for (i=;i<=len;i++)
a[i]*=b;
for (i=;i<=len;i++)
a[i+]+=a[i]/,a[i]%=;
int loc=len+;
while (a[loc])
{
a[loc+]+=a[loc]/;
a[loc]%=;
loc++;
}
len=loc-;
}
void print()
{int i;
for (i=len;i>=;i--) printf("%d",a[i]);
cout<<endl;
}
}ans;
int d[],du[],pri[],pre[],tot,n,cnt,sum,flag;
bool vis[];
int main()
{int i,j;
freopen("tree1.in","r",stdin);
freopen("1005.out","w",stdout);
cin>>n;
flag=;
for (i=;i<=n;i++)
{
scanf("%d",&d[i]);
if (d[i]!=-) cnt++,sum+=d[i]-;
if (d[i]==||d[i]==n) flag=;
}
if (n==)
{
cout<<;
return ;
}
if (n==)
{
if ((d[]==||d[]>)||(d[]==||d[]>))
cout<<;
else cout<<;
return ;
}
if (sum>n-)
{
cout<<;
return ;
}
if (flag)
{
cout<<;
return ;
}
for (i=;i<=n-;i++)
du[i]++;
for (i=;i<=n--sum;i++)
du[i]--;
for (i=;i<=n;i++)
if (d[i]!=-)
{
for (j=;j<=d[i]-;j++)
du[j]--;
}
for (i=;i<=n--sum;i++)
du[n-cnt]++; for (i=;i<=;i++)
{
if (vis[i]==)
{
pri[++tot]=i;
pre[i]=i;
}
for (j=;j<=tot;j++)
{
if (pri[j]*i>) break;
vis[i*pri[j]]=;
pre[i*pri[j]]=pri[j];
if (i%pri[j]==) break;
}
}
for (i=;i>=;i--)
if (pre[i]!=i)
{
du[pre[i]]+=du[i];
du[i/pre[i]]+=du[i];
du[i]=;
}
ans.a[]=;ans.len=;
for (i=;i<=;i++)
if (du[i]>)
{
for (j=;j<=du[i];j++)
ans*=i;
}
ans.print();
}