题目大意

如图

Data Constraint
$n\leq50$

题解

有一个叫prufer序列的东西
一个$n$个点的树会和一个长度为$n-2$的prufer序列一一对应，且满足序列中的出现次数+1就是点在树中的度数。
然后就可以考虑构造prufer序列来求方案。
设$f_{i,j,k}$表示处理完前$i$个点，树中已经$j$个点，当前构造的prufer序列长度为$k$.转移比较简单。
最后对于$x$的答案就是$f_{n,x,x-2}$

时间复杂度：$O(n^4)$

SRC

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std ;#define N 50 + 10
typedef long long ll ;
const int MO = 1e9 + 7 ;int a[N] ;
ll f[N][N][N] ;
ll fac[N] , _fac[N] ;
int T , n , maxd , ret ;int Power( int x , int k ) {int s = 1 ;while ( k ) {if ( k & 1 ) s = (ll)s * x % MO ;x = (ll)x * x % MO ;k /= 2 ;}return s ;
}ll C( int n , int m ) { return (ll)fac[n] * _fac[m] % MO * _fac[n-m] % MO ; }int main() {freopen( "a.in" , "r" , stdin ) ;freopen( "a.out" , "w" , stdout ) ;fac[0] = _fac[0] = 1 ;for (int i = 1 ; i <= 50 ; i ++ ) {fac[i] = fac[i-1] * i % MO ;_fac[i] = Power( fac[i] , MO - 2 ) ;}scanf( "%d" , &T ) ;while ( T -- ) {scanf( "%d" , &n ) ;for (int i = 1 ; i <= n ; i ++ ) scanf( "%d" , &a[i] ) ;memset( f , 0 , sizeof(f) ) ;f[0][0][0] = 1 ;for (int i = 1 ; i <= n ; i ++ ) {for (int j = 0 ; j <= i ; j ++ ) {for (int k = 0 ; k <= n ; k ++ ) {f[i][j][k] = f[i-1][j][k] ;if ( j ) {for (int l = 0 ; l <= min( a[i] - 1 , k ) ; l ++ ) {f[i][j][k] = (f[i][j][k] + (ll)f[i-1][j-1][k-l] * C( k , l ) % MO) % MO ;}}}}}printf( "%d " , n ) ;for (int i = 2 ; i <= n ; i ++ ) printf( "%lld " , f[n][i][i-2] ) ;printf( "\n" ) ;}return 0 ;
}

以上.