917D - Stranger Trees - CodeForces Solution

#include<iostream>
#include<fstream>
#include<vector>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 105
#define ll long long
#define mod 1000000007
using namespace std;

int n, k, p[N];
vector<int> son[N];
ll C[N][N], dp[N][N][2], pd[N][2], g[N];

ll qpow(ll a, int b){
ll ret = 1;
for(; b; b >>= 1){ if(b&1) (ret *= a) %= mod; (a *= a) %= mod; }
return ret;
}

void dfs(int x, int fa){
dp[x][1][0] = dp[x][1][1] = 1;
for(int y : son[x]) if(y != fa){
dfs(y, x);
rep(i,1,n) rep(j,1,n) rep(a,0,1) rep(b,0,1){
ll v = dp[x][i][a] * dp[y][j][b] % mod;
if(b) (pd[i+j][a] += v * n) %= mod;
if(a+b < 2) (pd[i+j-1][a+b] += v) %= mod;
}
rep(i,1,n) rep(p,0,1) dp[x][i][p] = pd[i][p], pd[i][p] = 0;
}
}

int main(){
cin>>n;
int u, v;
rep(i,2,n) cin>>u>>v, son[u].push_back(v), son[v].push_back(u);

C[0][0] = 1;
rep(i,1,n){
C[i][0] = 1;
rep(j,1,i) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
dfs(1, 0);
rep(i,1,n){
g[i] = dp[1][i][1] * qpow(n, mod-2) % mod;
rep(j,1,i-1) (g[i] += mod - C[n-i+j][j] * g[i-j] % mod) %= mod;
}
per(i,n,1) cout<< g[i] <<" \n"[i == 1];
return 0;
}