G2A Many GEOs
SHARE
TWEET

Untitled

a guest Mar 28th, 2020 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=1e5+1;
  5. const ll mod=1e9+7;
  6. int rt;
  7. #define fi first
  8. #define se second
  9. int n;
  10. int ptr=0;
  11. int a[N];
  12. int st[N],en[N];
  13. vector<int>adj[N];
  14. int sz[N];
  15. int bc[N],bs[N];
  16. void dfs(int id,int p){
  17.     a[++ptr]=id;
  18.     st[id]=ptr;
  19.     sz[id]=1;
  20.     bs[id]=id;
  21.     for(auto cur:adj[id]){
  22.         if(cur==p) continue;
  23.         dfs(cur,id);
  24.         sz[id]+=sz[cur];
  25.         if(sz[cur]>sz[bc[id]]) bc[id]=cur,bs[id]=bs[cur];
  26.     }
  27.     en[id]=ptr;
  28.     //cout << id << ' ' << st[id] << ' ' << en[id] << endl;
  29. }
  30. int m0[N];
  31. int m1[N],m2[N],m3[N];
  32. int b1[N],b2[N],b3[N];
  33. void dfs2(int id,int p){
  34.     m0[id]=st[id];
  35.     for(auto cur:adj[id]){
  36.         if(cur==p) continue;
  37.         dfs2(cur,id);
  38.         m0[id]=max(m0[id],m0[cur]);
  39.         if(m3[id]<m0[cur]) m3[id]=m0[cur],b3[id]=cur;
  40.         if(m2[id]<m3[id]) swap(m2[id],m3[id]),swap(b2[id],b3[id]);
  41.         if(m1[id]<m2[id]) swap(m1[id],m2[id]),swap(b1[id],b2[id]);
  42.     }
  43.    
  44. }
  45. void dfs3(int id,int p,int z){
  46.     if(m3[id]<z) m3[id]=z,b3[id]=p;
  47.     if(m2[id]<m3[id]) swap(m2[id],m3[id]),swap(b2[id],b3[id]);
  48.     if(m1[id]<m2[id]) swap(m1[id],m2[id]),swap(b1[id],b2[id]);
  49.     //cout << id << endl;
  50.     //cout << m1[id] << ' ' << m2[id] << endl;
  51.     for(auto cur:adj[id]){
  52.         if(cur==p) continue;
  53.         if(b1[id]==cur) dfs3(cur,id,max(m2[id],st[id]));
  54.         else dfs3(cur,id,max(m1[id],st[id]));
  55.     }
  56. }
  57. int c1[N],c2[N];
  58. int d1[N],d2[N];
  59. int e1[N],e2[N];
  60. int f1[N],f2[N];
  61. int d0[N];
  62. void dfs4(int id,int p){
  63.     e1[id]=e2[id]=1e9;
  64.     for(auto cur:adj[id]){
  65.         if(cur==p) continue;
  66.         dfs4(cur,id);
  67.         int z=e1[cur]+1;
  68.         if(adj[cur].size()>=3) z=1;
  69.         if(e2[id]>z) e2[id]=z,f2[id]=cur;
  70.         if(e1[id]>e2[id]) swap(e1[id],e2[id]),swap(f1[id],f2[id]);
  71.         if(z>=1e9) continue;
  72.         if(c2[id]<en[cur]) c2[id]=en[cur],d2[id]=z;
  73.         if(c1[id]<c2[id]) swap(c1[id],c2[id]),swap(d1[id],d2[id]);
  74.     }
  75. }
  76. void dfs5(int id,int p){
  77.     for(auto cur:adj[id]){
  78.         if(cur==p) continue;
  79.         if(f1[id]==cur) d0[cur]=min(d0[id],e2[id])+1;
  80.         else  d0[cur]=min(d0[id],e1[id])+1;
  81.         if(adj[id].size()>=3) d0[cur]=1;
  82.         dfs5(cur,id);
  83.     }
  84. }
  85. int g[N];
  86. vector<pair<int,int> >v[N];
  87. void dfs6(int id,int p){
  88.     for(auto cur:adj[id]){
  89.         if(cur==p) continue;
  90.         dfs6(cur,id);
  91.     }
  92.     if(id==rt) return;
  93.     int w1=(b1[id]==p || b2[id]==p)?m3[id]:m2[id];
  94.     int w2=(b1[p]==id || b2[p]==id)?m3[p]:m2[p];
  95.     int w3=c1[id]-d1[id]-1;
  96.     int w4=(c1[p]==en[id])?c2[p]-d2[p]-1:c1[p]-d1[p]-1;
  97.     int ans=max(max(w1,w2),max(w3,w4));
  98.     if(d0[id]<1e9){
  99.         int z=en[p];
  100.         if(n-z>=d0[p]+2) ans=max(ans,n-d0[p]-1);
  101.         else ans=max(ans,st[p]-(d0[p]+2-(n-z)));
  102.     }
  103.     //cout << "f " << id << ' ' << ans << endl;
  104. //  cout << w1 << ' ' << w2 << ' ' << w3 << ' ' << w4 << endl;
  105.     if(ans>st[id]){
  106.         //cout << ans << ' ' << id << ' ' << p << endl;
  107.         v[ans].push_back({id,p});
  108.     }
  109. }
  110. void dfs7(int id,int p){
  111.     for(auto cur:adj[id]){
  112.         if(cur==p) continue;
  113.         dfs7(cur,id);
  114.     }
  115.     if(adj[id].size()<=2) return;
  116.     int z=p,y=p;
  117.     for(auto cur:adj[id]){
  118.         if(cur==p) continue;
  119.         if(en[cur]==n) z=cur;
  120.         if(en[cur]>=n-1 && st[cur]<=n-1) y=cur;
  121.     }
  122.     if(y!=z){
  123.         //cout << "!!! " << id << endl;
  124.         for(auto cur:adj[id]){
  125.             if(cur==y || cur==z) continue;
  126.             //cout << n-2 << ' ' << z << ' ' << cur << endl;
  127.             v[n-2].push_back({z,cur});
  128.         }
  129.         return;
  130.     }
  131.     //cout << "??? " << id << endl;
  132.     vector<int>bona;
  133.     for(auto cur:adj[id]){
  134.         if(cur==z) continue;
  135.         bona.push_back(cur);
  136.     }
  137.     for(int i=1; i<bona.size() ;i++){
  138.         //cout << n-1 << ' ' << bona[0] << ' ' << bona[i] << endl;
  139.         v[n-1].push_back({bona[0],bona[i]});
  140.     }
  141.     int b2=0;
  142.     for(auto cur:adj[id]){
  143.         if(cur==p){
  144.             if(en[id]==n) b2=max(b2,st[id]-1);
  145.         }
  146.         else if(en[cur]!=n) b2=max(b2,en[cur]);
  147.     }
  148.     v[b2-1].push_back({bona[0],z});
  149. }
  150. int p[2*N],dz[2*N];
  151. int find(int x){
  152.     if(p[x]!=x) p[x]=find(p[x]);
  153.     return p[x];
  154. }
  155. ll ans=1;
  156. ll f[N],inf[N];
  157. ll pw(ll x,ll y){
  158.     if(y==0) return 1;
  159.     if(y%2) return x*pw(x,y-1)%mod;
  160.     ll res=pw(x,y/2);
  161.     return res*res%mod;
  162. }
  163. void gg(){
  164.     f[0]=1;inf[0]=1;
  165.     for(int i=1; i<=n ;i++) f[i]=f[i-1]*i%mod;
  166.     inf[n]=pw(f[n],mod-2);
  167.     for(int i=n; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
  168. }
  169. ll C(int x,int y){
  170.     return f[x]*inf[y]%mod*inf[x-y]%mod;
  171. }
  172. void join(int x,int y){
  173.     x=find(x);y=find(y);
  174.     if(x==y) return;
  175.     if(dz[x]>=0 && dz[y]>=0) ans=ans*C(dz[x]+dz[y],dz[y])%mod;
  176.     else ans=ans*pw(dz[x]+dz[y]+1,mod-2)%mod;
  177.     dz[y]+=dz[x];
  178.     p[x]=y;
  179. }
  180. int main(){
  181.     ios::sync_with_stdio(false);
  182.     freopen("circus.in","r",stdin);
  183.     freopen("circus.out","w",stdout);
  184.     cin >> n;gg();
  185.     for(int i=1; i<n ;i++){
  186.         int u,v;cin >> u >> v;
  187.         adj[u].push_back(v);
  188.         adj[v].push_back(u);
  189.     }
  190.     for(int i=1; i<=n ;i++){
  191.         if(adj[i].size()==1) rt=i;
  192.     }
  193.     dfs(rt,0);
  194.     dfs2(rt,0);
  195.     dfs3(rt,0,0);
  196.     dfs4(rt,0);
  197.     d0[rt]=1e9;
  198.     dfs5(rt,0);
  199.     dfs6(rt,0);
  200.     dfs7(rt,0);
  201.     for(int i=1; i<=n ;i++){
  202.         p[i]=i;p[n+i]=n+i;
  203.         dz[i]=1;dz[n+i]=-1;
  204.     }
  205.     ans=1;
  206.     for(int i=n; i>=1 ;i--){
  207.         g[i]=ans;
  208.         join(a[i],n+a[i]);
  209.         for(auto cur:v[i]){
  210.             if(st[cur.fi]<i && st[cur.se]<i) join(cur.fi,cur.se);
  211.            
  212.         }
  213.     }
  214.     for(int i=1; i<=n ;i++){
  215.         cout << f[i]*pw(g[i],mod-2)%mod << '\n';
  216.     }
  217. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top