SO EASY
2024-11-23 21:17:17
发布于:北京
0阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int ksm(int x,int y){
int z=1;
for(;y;x=1ll*x*x%mod,y>>=1)if(y&1)z=1ll*z*x%mod;
return z;
}
int n,fac[100100],inv[100100],res[100100];
vector<int>g[100100],key;
struct dsu{
int fa,ins,out;
}a[100100];
void init(){
for(int i=1;i<=n;i++)if(g[i].size()!=2)a[i].fa=i,a[i].out=g[i].size(),key.push_back(i);
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int find(int x){
return a[x].fa==x?x:a[x].fa=find(a[x].fa);
}
void merge(int x,int y,int z){
x=find(x),y=find(y);
if(x==y)return;
key.erase(lower_bound(key.begin(),key.end(),y));
a[x].ins+=a[y].ins+z-1,a[x].out+=a[y].out-2,a[y].fa=x;
}
struct path{
int x,y,z;
path(int u,int v,int w){x=u,y=v,z=w;}
friend bool operator <(const path &x,const path &y){
return x.z<y.z;
}
};
vector<path>paths;
void getpath(int x,int fa,int len,int from){
if(g[x].size()!=2){
if(from)paths.push_back(path(from,x,len));
len=1,from=x;
}
for(auto y:g[x])if(y!=fa)getpath(y,x,len+1,from);
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),g[x].push_back(y),g[y].push_back(x);
init();
getpath(key.front(),0,0,0);
sort(paths.begin(),paths.end());
for(int i=n-1,j=0;i;i--){
while(j<paths.size()&&i<n-paths[j].z)merge(paths[j].x,paths[j].y,paths[j].z),j++;
res[i]=fac[i];
for(auto x:key)res[i]=1ll*res[i]*inv[i-(n-a[x].ins-1)+a[x].out*(n-i-1)]%mod;
}
res[n]=fac[n];
for(int i=1;i<=n;i++)printf("%d\n",res[i]);
return 0;
}
这里空空如也
有帮助,赞一个