1 条题解
-
1
C++ :
#include<bits/stdc++.h> using namespace std; const int N=214514; const int mod=1e9+7; #define rep(i,j,k) for(int i=(j);i<=(k);i++) #define ll long long struct edge{int v,nt;}e[N<<1]; ll msk(ll a,ll b){ll k=1; while(b){if(b&1)k=k*a%mod;a=a*a%mod,b>>=1;}return k; }ll sz[N],g[N],fac; int n,tot,hd[N]; void add(int x,int y){e[++tot].v=y,e[tot].nt=hd[x];hd[x]=tot;} void dfs(int x,int fa){sz[x]=1; for(int i=hd[x],to;i;i=e[i].nt)if((to=e[i].v)!=fa){ dfs(to,x);sz[x]+=sz[to]; }g[1]=g[1]*sz[x]%mod; }void solve(int x,int fa){ if(fa){g[x]=g[fa]*(n-sz[x])%mod*msk(sz[x],mod-2)%mod;} for(int i=hd[x],to;i;i=e[i].nt)if((to=e[i].v)!=fa){ solve(to,x); } }int main(){scanf("%d",&n);int x,y;g[1]=fac=1; rep(i,1,n-1)scanf("%d%d",&x,&y),add(x,y),add(y,x),fac=fac*i%mod; dfs(1,0);solve(1,0);fac=fac*n%mod; rep(i,1,n)printf("%lld\n",fac*msk(g[i],mod-2)%mod); }
- 1
信息
- ID
- 12836
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 8
- 标签
- 递交数
- 53
- 已通过
- 8
- 上传者