bzoj 1211: [HNOI2004]树的计数

.

题意：给出每个节点的度数，问有多少棵树满足这些度数。
题解：Prüfer序列+组合数学
Prüfer序列是由标号树产生的唯一数列。生成方法：

一棵树要得到普吕弗序列，方法是逐次去掉树的顶点，直到剩下两个顶点。考虑树T，其顶点为{1, 2, …, n}。在第i步，去掉标号最小的叶，并把普吕弗序列的第i项设为这叶的邻顶点的标号。

序列和树是一一对应的，而每个点的度数-1就是这个点在Prüfer序列中出现的次数。排列组合搞一搞就好了。
代码：

#include<cstdio>
#include<cstring>

int n,d[160],s[34],sum=0,prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139};

void wk(int x,int y)
{
    for(int j=0;j<34;j++)
    {
        while(x%prime[j]==0)
        {
            x/=prime[j];
            s[j]+=y;
        }
    }
}
int main()
{
    scanf("%d",&n);
    if(n==1)
    {
        int x;
        scanf("%d",&x);
        if(x==0)
        puts("1");
        else
        puts("0");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        if(!d[i])
        {
            puts("0");
            return 0;
        }
        sum+=d[i];
    }
    if(sum!=(n-1<<1))
    {
        puts("0");
        return 0;
    }
    for(int i=1;i<n-1;i++)
    {
        wk(i,1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<d[i];j++)
        wk(j,-1);
    }
    long long ans=1;
    for(int i=0;i<34;i++)
    {
        for(int j=0;j<s[i];j++)
        ans*=prime[i];
    }
    printf("%lld",ans);
}