Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.95 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement