题意: 就是给你一个压缩图的方式,然后让你计算任意选择k(1....n)个点之后的图上剩余点的期望数(mod 1e9+7).

做法:
很显然的得到两个结论(记当前要保留的点为k,总点数为n).
1.对于一个度数小于等于2的点,他的留下来的概率为(n-1,k-1)/(n,k). 因为只有这个点被选到了,才有可能留下来.
2.对于一个度数大于2的点,他留下来的有两种情况,一种是他被选到了, 还有就是他有3个及以上的儿子所在的子树中有点被选到.那么可以得出其概率为 1 -( \sum_{i<j}(si_i + si_j, k) + (m-2) * \sum_i(si_i,k) ) / (N, k)  (注:这里反着算了一下用1去减不满足的概率). 其中m为当前点儿子的个数,其儿子所在的子树的大小分别为[si_1, si_2, si_3...., si_m].

我们所求的期望数即为所有点保留的概率的和.
对于第1类的点我们可以很方便的维护,直接加入到答案中或者统计他的数量最后一起加.
对于第2类的点,难以维护的就是\sum_{i<j}(si_i + si_j, k),其他的数值都是可以直接加到答案上的. 首先我们要考虑到 si_i + si_j 的最大值为n,那么我们就可以用cnt[]去维护,cnt[x]表示si_i+si_j = x的数量, 那么我们就可以暴力的统计cnt   (O(n2)).
然后对于每一个k,统一加入到答案中(O(n2)).
这样我们就可以算出所有的答案了.
具体的过程见代码.

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,o<<1
#define rson mid+1,r,o<<1|1
#define fio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
typedef pair<int, int> P;
typedef pair<PII, int> PIII;
const LL INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
const int M = 11;
const LL mod = 1e9 + 7;
const double PI=acos(-1);
inline int ab(int x){return x < 0 ? -x : x;}
inline LL mm(LL x){return x >= mod ? x - mod : x < 0 ? x + mod : x;}


int F[N], Finv[N], inv[N];
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % mod;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % mod;
    }
}
int comb(int n, int m){
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % mod * Finv[m] % mod;
}
int invcomb(int n, int m){
    if(m < 0 || m > n) return 0;
    return Finv[n] * 1ll * F[n - m] % mod * F[m] % mod;
}
vector<int>son[N];
int si[N];
int n;
int cnt[N], tot = 0;
int ans[N];
void dfs(int o, int fa){
    si[o] = 1;
    LL sum[N];
    for(int i = 0; i <= n; ++i) sum[i] = 0;
    for(auto it : son[o]){
        if(it == fa)    continue;
        dfs(it, o);
        si[o] += si[it];
    }
    if(son[o].size() <= 2)  tot++;
    else{
        for(int i = 0; i < son[o].size(); ++i){
            if(son[o][i] == fa)    continue;
            for(int j = 0; j < i; ++j){
                if(son[o][j] == fa) continue;
                cnt[si[son[o][i]] + si[son[o][j]]]++;
            }
            for(int k = 1; k <= n; ++k){
                ans[k] += (son[o].size() - 2) * 1ll * comb(si[son[o][i]], k) % mod;
                if(ans[k] >= mod)   ans[k] -= mod;
            }
        }
        if(o != 1){
            for(int j = 0; j < son[o].size(); ++j){
                if(son[o][j] == fa) continue;
                cnt[n - si[o] + si[son[o][j]]]++;
            }
            for(int k = 1; k <= n; ++k){
                ans[k] += (son[o].size() - 2) * 1ll * comb(n - si[o], k) % mod;
                if(ans[k] >= mod)   ans[k] -= mod;
            }
        }
    }
}
int main()
{
    init();
    int u, v;
    scanf("%d", &n);
    for(int i = 1; i < n; ++i){
        scanf("%d%d", &u, &v);
        son[u].push_back(v);
        son[v].push_back(u);
    }
    dfs(1, 1);
    for(int k = 1; k <= n; ++k){
        ans[k] += tot * 1ll * comb(n - 1, k -1) % mod;
        if(ans[k] >= mod)   ans[k] -= mod;
        for(int i = k; i <= n; ++i){
            ans[k] -= cnt[i] * 1ll * comb(i, k) % mod;
            if(ans[k] < 0)   ans[k] += mod;
        }
        ans[k] = ans[k] * 1ll * invcomb(n, k) % mod;
        ans[k] += n - tot;
        if(ans[k] >= mod)   ans[k] -= mod;
        printf("%d\n", ans[k]);
    }
    return 0;
}