题解

“简单”

#include <bits/stdc++.h>
using namespace std;
const int N=100007,P=1000000007;

int n,fa[N],size[N],num[N],ifac[N],ans[N];
vector<int>e[N];
set<int>root;

struct edge{
    int u,v,w;
};vector<edge>vec;
int read(){
    int x=0,c=getchar();
    while(isspace(c)) c=getchar();
    while(isdigit(c)) (x*=10)+=c&15,c=getchar();
    return x;
}

void inc(int&a,int b){
    a+=b-P,a+=a>>31&P;
}

int mul(int a,int b){
    return 1ll*a*b%P;
}

int pow(int a,int b){
    int r=1;
    for(;b;b>>=1,a=mul(a,a)){
        if(b&1)r=mul(a,r);
    }
    return r;
}

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

void dfs(int u,int fa,int dep,int root){
    for(int v:e[u]){
        if(v^fa){
            if(e[v].size()==2){
                dfs(v,u,dep+1,root);
            } else if(root<v) {
                vec.push_back({root,v,dep+1});
            }
        }
    }
}

int main(){
    int n=read();
    for(int i=ans[0]=ifac[0]=1;i<=n;++i){
        ifac[i]=pow(ans[i]=mul(ans[i-1],i),P-2);
    }
    for(int i=1,u,v;i<n;++i){
        u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    }
    for(int u=1;u<=n;++u){
        if(e[u].size()^2){
            num[fa[u]=u]=e[u].size(),dfs(u,0,1,u),size[u]=1,root.insert(u);
        }
    }
    sort(vec.begin(),vec.end(),[](edge a,edge b){return a.w>b.w;});
    for(int i=n-1;i;--i){
        for(int u,v;vec.size()&&vec.back().w+i<n;vec.pop_back()){
	    	u=find(vec.back().u),v=find(vec.back().v),size[u]+=size[v]+vec.back().w-2,num[u]+=num[v]-2,root.erase(v),fa[v]=u;
        }
        for(int x:root){
            ans[i]=mul(ans[i],ifac[i-n+size[x]+(n-i-1)*num[x]]);
        }
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<endl;
    }
    return 0;
}