Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=1e5+1;
- const ll mod=1e9+7;
- int rt;
- #define fi first
- #define se second
- int n;
- int ptr=0;
- int a[N];
- int st[N],en[N];
- vector<int>adj[N];
- int sz[N];
- int bc[N],bs[N];
- void dfs(int id,int p){
- a[++ptr]=id;
- st[id]=ptr;
- sz[id]=1;
- bs[id]=id;
- for(auto cur:adj[id]){
- if(cur==p) continue;
- dfs(cur,id);
- sz[id]+=sz[cur];
- if(sz[cur]>sz[bc[id]]) bc[id]=cur,bs[id]=bs[cur];
- }
- en[id]=ptr;
- //cout << id << ' ' << st[id] << ' ' << en[id] << endl;
- }
- int m0[N];
- int m1[N],m2[N],m3[N];
- int b1[N],b2[N],b3[N];
- void dfs2(int id,int p){
- m0[id]=st[id];
- for(auto cur:adj[id]){
- if(cur==p) continue;
- dfs2(cur,id);
- m0[id]=max(m0[id],m0[cur]);
- if(m3[id]<m0[cur]) m3[id]=m0[cur],b3[id]=cur;
- if(m2[id]<m3[id]) swap(m2[id],m3[id]),swap(b2[id],b3[id]);
- if(m1[id]<m2[id]) swap(m1[id],m2[id]),swap(b1[id],b2[id]);
- }
- }
- void dfs3(int id,int p,int z){
- if(m3[id]<z) m3[id]=z,b3[id]=p;
- if(m2[id]<m3[id]) swap(m2[id],m3[id]),swap(b2[id],b3[id]);
- if(m1[id]<m2[id]) swap(m1[id],m2[id]),swap(b1[id],b2[id]);
- //cout << id << endl;
- //cout << m1[id] << ' ' << m2[id] << endl;
- for(auto cur:adj[id]){
- if(cur==p) continue;
- if(b1[id]==cur) dfs3(cur,id,max(m2[id],st[id]));
- else dfs3(cur,id,max(m1[id],st[id]));
- }
- }
- int c1[N],c2[N];
- int d1[N],d2[N];
- int e1[N],e2[N];
- int f1[N],f2[N];
- int d0[N];
- void dfs4(int id,int p){
- e1[id]=e2[id]=1e9;
- for(auto cur:adj[id]){
- if(cur==p) continue;
- dfs4(cur,id);
- int z=e1[cur]+1;
- if(adj[cur].size()>=3) z=1;
- if(e2[id]>z) e2[id]=z,f2[id]=cur;
- if(e1[id]>e2[id]) swap(e1[id],e2[id]),swap(f1[id],f2[id]);
- if(z>=1e9) continue;
- if(c2[id]<en[cur]) c2[id]=en[cur],d2[id]=z;
- if(c1[id]<c2[id]) swap(c1[id],c2[id]),swap(d1[id],d2[id]);
- }
- }
- void dfs5(int id,int p){
- for(auto cur:adj[id]){
- if(cur==p) continue;
- if(f1[id]==cur) d0[cur]=min(d0[id],e2[id])+1;
- else d0[cur]=min(d0[id],e1[id])+1;
- if(adj[id].size()>=3) d0[cur]=1;
- dfs5(cur,id);
- }
- }
- int g[N];
- vector<pair<int,int> >v[N];
- void dfs6(int id,int p){
- for(auto cur:adj[id]){
- if(cur==p) continue;
- dfs6(cur,id);
- }
- if(id==rt) return;
- int w1=(b1[id]==p || b2[id]==p)?m3[id]:m2[id];
- int w2=(b1[p]==id || b2[p]==id)?m3[p]:m2[p];
- int w3=c1[id]-d1[id]-1;
- int w4=(c1[p]==en[id])?c2[p]-d2[p]-1:c1[p]-d1[p]-1;
- int ans=max(max(w1,w2),max(w3,w4));
- if(d0[id]<1e9){
- int z=en[p];
- if(n-z>=d0[p]+2) ans=max(ans,n-d0[p]-1);
- else ans=max(ans,st[p]-(d0[p]+2-(n-z)));
- }
- //cout << "f " << id << ' ' << ans << endl;
- // cout << w1 << ' ' << w2 << ' ' << w3 << ' ' << w4 << endl;
- if(ans>st[id]){
- //cout << ans << ' ' << id << ' ' << p << endl;
- v[ans].push_back({id,p});
- }
- }
- void dfs7(int id,int p){
- for(auto cur:adj[id]){
- if(cur==p) continue;
- dfs7(cur,id);
- }
- if(adj[id].size()<=2) return;
- int z=p,y=p;
- for(auto cur:adj[id]){
- if(cur==p) continue;
- if(en[cur]==n) z=cur;
- if(en[cur]>=n-1 && st[cur]<=n-1) y=cur;
- }
- if(y!=z){
- //cout << "!!! " << id << endl;
- for(auto cur:adj[id]){
- if(cur==y || cur==z) continue;
- //cout << n-2 << ' ' << z << ' ' << cur << endl;
- v[n-2].push_back({z,cur});
- }
- return;
- }
- //cout << "??? " << id << endl;
- vector<int>bona;
- for(auto cur:adj[id]){
- if(cur==z) continue;
- bona.push_back(cur);
- }
- for(int i=1; i<bona.size() ;i++){
- //cout << n-1 << ' ' << bona[0] << ' ' << bona[i] << endl;
- v[n-1].push_back({bona[0],bona[i]});
- }
- int b2=0;
- for(auto cur:adj[id]){
- if(cur==p){
- if(en[id]==n) b2=max(b2,st[id]-1);
- }
- else if(en[cur]!=n) b2=max(b2,en[cur]);
- }
- v[b2-1].push_back({bona[0],z});
- }
- int p[2*N],dz[2*N];
- int find(int x){
- if(p[x]!=x) p[x]=find(p[x]);
- return p[x];
- }
- ll ans=1;
- ll f[N],inf[N];
- ll pw(ll x,ll y){
- if(y==0) return 1;
- if(y%2) return x*pw(x,y-1)%mod;
- ll res=pw(x,y/2);
- return res*res%mod;
- }
- void gg(){
- f[0]=1;inf[0]=1;
- for(int i=1; i<=n ;i++) f[i]=f[i-1]*i%mod;
- inf[n]=pw(f[n],mod-2);
- for(int i=n; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
- }
- ll C(int x,int y){
- return f[x]*inf[y]%mod*inf[x-y]%mod;
- }
- void join(int x,int y){
- x=find(x);y=find(y);
- if(x==y) return;
- if(dz[x]>=0 && dz[y]>=0) ans=ans*C(dz[x]+dz[y],dz[y])%mod;
- else ans=ans*pw(dz[x]+dz[y]+1,mod-2)%mod;
- dz[y]+=dz[x];
- p[x]=y;
- }
- int main(){
- ios::sync_with_stdio(false);
- freopen("circus.in","r",stdin);
- freopen("circus.out","w",stdout);
- cin >> n;gg();
- for(int i=1; i<n ;i++){
- int u,v;cin >> u >> v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- for(int i=1; i<=n ;i++){
- if(adj[i].size()==1) rt=i;
- }
- dfs(rt,0);
- dfs2(rt,0);
- dfs3(rt,0,0);
- dfs4(rt,0);
- d0[rt]=1e9;
- dfs5(rt,0);
- dfs6(rt,0);
- dfs7(rt,0);
- for(int i=1; i<=n ;i++){
- p[i]=i;p[n+i]=n+i;
- dz[i]=1;dz[n+i]=-1;
- }
- ans=1;
- for(int i=n; i>=1 ;i--){
- g[i]=ans;
- join(a[i],n+a[i]);
- for(auto cur:v[i]){
- if(st[cur.fi]<i && st[cur.se]<i) join(cur.fi,cur.se);
- }
- }
- for(int i=1; i<=n ;i++){
- cout << f[i]*pw(g[i],mod-2)%mod << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement