做法1：
考虑矩阵树定理，令树上的边边权为$x$，非树边边权为1，以此得到矩阵$M$，则$\det(M)$的$k$次项系数恰为含有$k$条树边的方案数
关于求$\det(M)$这个多项式，可以暴力插$x\in [0,n]$并通过高斯消元求出其答案，再通过拉格朗日插值法求出此多项式，复杂度为$o(n^{4})$
做法2：
考虑暴力枚举树上的$k$条边，其将原图分为$n-k$个连通块，假设其中第$i$个连通块点数为$x_{i}$，下面求出此时对应的树的数量（忽略其余树边不能被选的条件）——
（为了方便，以下令$m=n-k$，即连通块数）
将一个连通块作为一个点，枚举第$i$个连通块的度$r_{i}$，根据perfer序列，即要求$i$在长为$m-2$的序列中恰好出现$r_{i}-1$次，可得此时对应的方案数为$\frac{(m-2)!}{\prod_{i=1}^{m}(r_{i}-1)!}$
（对于度数，要求$\sum_{i=1}^{m}(r_{i}-1)=m-2$）
另外每一条边在对应连通块还有$x_{i}$个选择，总答案即
$$
\sum_{r_{i}\in Z^{+},\sum_{i=1}^{m}(r_{i}-1)=m-2}\frac{(m-2)!\prod_{i=1}^{m}x_{i}^{r_{i}}}{\prod_{i=1}^{m}(r_{i}-1)!}
$$
考虑$(\sum_{i=1}^{m}x_{i})^{m-2}$，以$r_{i}-1$作为每一个的次数，答案即
$$
\sum_{r_{i}\in Z^{+},\sum_{i=1}^{m}(r_{i}-1)=m-2}\frac{(m-2)!\prod_{i=1}^{m}x_{i}^{r_{i}+1}}{\prod_{i=1}^{m}(r_{i}-1)!}
$$
对比两式，发现前者即后者乘上$\prod_{i=1}^{m}x_{i}$，因此对应的树的数量即$n^{m-2}\prod_{i=1}^{m}x_{i}$（显然有$\sum_{i=1}^{m}x_{i}=n$）
关于$\prod_{i=1}^{m}x_{i}$，即可看作每一个连通块内选择一个点，因此即对原树进行树形dp——
令$f_{i,j,0/1}$表示以$i$为根的子树中、选择$j$条边、与$i$相连的连通块是否选择对应的点，转移即类似背包，复杂度即是$o(n^{2})$的（每一个点转移到父亲的复杂度为$sz_{k}(sz_{fa}-sz_{k})$）
令$S_{i}=n^{n-i-2}f_{1,i,1}$，$ans_{i}$为答案，注意到我们忽略了其余树边也不能被选择的条件，因此$S_{i}$并不是真正的答案，而不难得到其与$ans_{i}$有以下关系：$S_{i}=\sum_{j=i}^{n-1}{j\choose i}ans_{j}$
（关于这个式子，$j$即枚举所有树中其最后实际上选的边数，其贡献即${j\choose i}ans_{j}$）
由此，从后往前以此求出$ans_{i}$即可
这一做法的时间复杂度为$o(n^{2})$，更为优秀（代码中即此做法）
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 105
4 #define mod 1000000007
5 struct Edge{
6 int nex,to;
7 }edge[N<<1];
8 int E,n,m,x,y,head[N],sz[N],f[N][N][2],g[N][2],c[N][N],ans[N];
9 void add(int x,int y){
10 edge[E].nex=head[x];
11 edge[E].to=y;
12 head[x]=E++;
13 }
14 void dfs(int k,int fa){
15 sz[k]=f[k][0][0]=f[k][0][1]=1;
16 for(int i=head[k];i!=-1;i=edge[i].nex)
17 if (edge[i].to!=fa){
18 dfs(edge[i].to,k);
19 for(int j=0;j<sz[k];j++){
20 g[j][0]=f[k][j][0],g[j][1]=f[k][j][1];
21 f[k][j][0]=f[k][j][1]=0;
22 }
23 for(int j=0;j<sz[k];j++)
24 for(int l=0;l<sz[edge[i].to];l++){
25 f[k][j+l][0]=(f[k][j+l][0]+1LL*g[j][0]*f[edge[i].to][l][1])%mod;
26 f[k][j+l][1]=(f[k][j+l][1]+1LL*g[j][1]*f[edge[i].to][l][1])%mod;
27 f[k][j+l+1][0]=(f[k][j+l+1][0]+1LL*g[j][0]*f[edge[i].to][l][0])%mod;
28 f[k][j+l+1][1]=(f[k][j+l+1][1]+1LL*g[j][0]*f[edge[i].to][l][1]+1LL*g[j][1]*f[edge[i].to][l][0])%mod;
29 }
30 sz[k]+=sz[edge[i].to];
31 }
32 }
33 int main(){
34 scanf("%d",&n);
35 memset(head,-1,sizeof(head));
36 for(int i=1;i<n;i++){
37 scanf("%d%d",&x,&y);
38 add(x,y);
39 add(y,x);
40 }
41 dfs(1,0);
42 for(int i=0;i<n;i++)
43 if (i==n-1)ans[i]=1;
44 else{
45 ans[i]=f[1][i][1];
46 for(int j=1;j<=n-i-2;j++)ans[i]=1LL*ans[i]*n%mod;
47 }
48 for(int i=0;i<n;i++){
49 c[i][0]=c[i][i]=1;
50 for(int j=1;j<i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
51 }
52 for(int i=n-1;i>=0;i--)
53 for(int j=i+1;j<n;j++)ans[i]=(ans[i]-1LL*ans[j]*c[j][i]%mod+mod)%mod;
54 for(int i=0;i<n;i++)printf("%d ",ans[i]);
55 }
View Code