题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5629
题意：
给你n个点，每个点的度数最多为a[i]
然后分别问你点数为s的树，一共有多少种，(1<=s<=n)
解法：
知道点的度数求可以构造的树的数量一般用到Purfer序列，因为一个长度为n-2的Purfer序列唯一对应一个n个点的树，且Purfer序列中i出现的次数就是节点i的度数减一，此题只给出点度数的上限，所以可以考虑dp
用dp[i][j][j]表示从前i个点中选取j个点且这j个点在Purfer序列中出现k次的合法Purfer序列数（也就是合法树的数量），考虑第i个点是否被选，以及被选后在Purfer序列出现的次数有以下转移方程：
dp[i][j][k]+=dp[i-1][j][k]（不选i）
dp[i][j+1][k+d]+=C[k+d][d]*dp[i-1][j][k]，d=0,1,…,a[i]-1（选i，出现d次，组合数C(k+d,d)表示在一个已经有序的长度为k的序列中插入d个相同的数的方案数）
dp[n][i][i-2]即为答案(1<=i<=n)

复杂度；O(n^4)

//HDU 5629

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 62;
int dp[maxn][maxn][maxn];
///考虑到了第i个点，现在出现了j个数，长度为k的方案数
long long c[maxn][maxn];
int n, a[maxn];

int main()
{
    for(int i = 0; i < maxn; i++){
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++){
            c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod;
        }
    }
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                for(int k = 0; k <= n-2; k++){
                    dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k])%mod;
                    for(int d = 0; d < a[i] && k + d <= n - 2; d++){
                        dp[i][j+1][k+d] = (dp[i][j+1][k+d] + c[k+d][d]*dp[i-1][j][k]%mod)%mod;
                    }
                }
            }
        }
        printf("%d", n);
        for(int i = 2; i <= n; i++){
            printf(" %d", dp[n][i][i-2]);
        }
        printf("\n");
    }
    return 0;
}