题目传送门
分析：
我们设恰好(k)条边不重复的方案数为(f(k))
再设钦定(n-k-1)条边与原来树上的边重合，剩下的边自由连接成树的方案数(g(k))
于是得到一个公式：
[g(k)=sum_{i=0}^{k}inom{k}{i}f(i)
]
意义为枚举剩下的(K)条边有哪些不重合
于是我们二项式反演:
[f(k)=sum_{i=0}^{k}(-1)^{k-i}inom{k}{i}g(i)
]
知道了(g)我们就可以(O(n^2))求(f)
考虑(g(k))之中会有(k+1)个连通块，那么生成树的方案数为
[n^{k-1}prod_{i=1}^{k+1}a_i
]
其中(a_i)表示每个连通块的大小，即在此连通块里选择一个点向其他连通块连边
我们想知道(prod_{i=1}^{k+1}a_i)在所有情况下的总和
考虑(DP)
设(f[u][i][0/1])表示在(u)为根的子树下，已经钦定(sz[u]-i-1)条边，(u)所在连通块是否已选择了一个点
列出(DP)式子
设(g[i][0/1])为传递给下一次(DP)的临时变量
(g[j+k][0]=f[u][j][0]*f[v][k][0])钦定这条父子边，(u,v)属于同一连通块未被选择
(g[j+k][1]=f[u][j][0]*f[v][k][1]+f[u][j][1]*f[v][k][0])钦定这条父子边，(u,v)属于同一连通块其中被选择
(g[j+k+1][0]=f[u][j][0]*f[v][k][1])不钦定这条父子边，(u,v)不属于同一连通块，(v)必须被选择，(u)继承原来的状态
(g[j+k+1][1]=f[u][j][1]*f[v][k][1])不钦定这条父子边，(u,v)不属于同一连通块，(v)必须被选择，(u)继承原来的状态
总复杂度为(O(n^2))
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
#include<bitset>
#include<string>
#define maxn 205
#define MOD 1000000007
using namespace std;
inline long long getint()
{
long long num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n;
int sz[maxn];
int fir[maxn],nxt[maxn<<1],to[maxn<<1],cnt;
int f[maxn][maxn][2],g[maxn][2],ans[maxn],C[maxn][maxn];
inline int upd(int x){return x<MOD?x:x-MOD;}
inline int ksm(int num,int k)
{
int ret=1;
for(;k;k>>=1,num=1ll*num*num%MOD)if(k&1)ret=1ll*ret*num%MOD;
return ret;
}
inline void newnode(int u,int v)
{to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}
inline void dfs(int u,int fa)
{
sz[u]=f[u][0][0]=f[u][0][1]=1;
for(int i=fir[u];i;i=nxt[i])if(to[i]!=fa)
{
int v=to[i];dfs(v,u);
for(int j=0;j<=sz[u]+sz[v];j++)g[j][0]=g[j][1]=0;
for(int j=0;j<=sz[u];j++)for(int k=0;k<=sz[v];k++)
{
g[j+k][0]=(g[j+k][0]+1ll*f[u][j][0]*f[v][k][0])%MOD;
g[j+k][1]=(g[j+k][1]+1ll*f[u][j][0]*f[v][k][1]+1ll*f[u][j][1]*f[v][k][0])%MOD;
g[j+k+1][0]=(g[j+k+1][0]+1ll*f[u][j][0]*f[v][k][1])%MOD;
g[j+k+1][1]=(g[j+k+1][1]+1ll*f[u][j][1]*f[v][k][1])%MOD;
}
sz[u]+=sz[v];
for(int j=0;j<=sz[u];j++)f[u][j][0]=g[j][0],f[u][j][1]=g[j][1];
}
}
int main()
{
n=getint();
for(int i=1;i<n;i++)
{
int u=getint(),v=getint();
newnode(u,v),newnode(v,u);
}
for(int i=0;i<=n;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=upd(C[i-1][j-1]+C[i-1][j]);
}
dfs(1,1);
ans[0]=1;
for(int i=1;i<n;i++)ans[i]=1ll*f[1][i][1]*ksm(n,i-1)%MOD;
for(int i=0;i<n;i++)for(int j=0;j<i;j++)ans[i]=upd(ans[i]-1ll*C[n-1-j][i-j]*ans[j]%MOD+MOD);
for(int i=n-1;~i;i--)printf("%d ",ans[i]);
}
