sacgajcvs

Untitled

Mar 28th, 2020
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.25 KB | None | 0 0
  1. /*
  2. _____ _ _ _ _
  3. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  4. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  5. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  6. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  7.  
  8. */
  9. #include<bits/stdc++.h>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. #define ll long long
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define endl '\n'
  16. #define mii map<ll,ll>
  17. #define msi map<string,ll>
  18. #define mis map<ll, string>
  19. #define rep(i,a,b) for(ll i=a;i<b;i++)
  20. #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
  21. #define trav(a, x) for(auto& a : x)
  22. #define pii pair<ll,ll>
  23. #define vi vector<ll>
  24. #define vii vector<pair<ll, ll>>
  25. #define vs vector<string>
  26. #define all(a) (a).begin(),(a).end()
  27. #define F first
  28. #define S second
  29. #define sz(x) (ll)x.size()
  30. #define hell 1000000007
  31. #define lbnd lower_bound
  32. #define ubnd upper_bound
  33. #define max(a,b) (a>b?a:b)
  34. #define min(a,b) (a<b?a:b)
  35.  
  36. /* For Debugging */
  37. #define DEBUG cerr<<"\n>>>I'm Here<<<\n"<<endl;
  38. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
  39. #define what_is(x) cerr << #x << " is " << x << endl;
  40.  
  41. std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  42. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  43. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  44. #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
  45. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  46. using namespace __gnu_pbds;
  47. using namespace std;
  48. #define PI 3.141592653589793
  49. #define N 200005
  50. ll n;
  51. vi a[N];
  52. ll fact[N];
  53. ll dp1[N],dp2[N],dp3[N];
  54. ll expo(ll base, ll exponent, ll mod) { //return base^exponent modulo modulus
  55. ll ans = 1;
  56. while(exponent !=0 ) {
  57. if((exponent&1) == 1) {
  58. ans = ans*base ;
  59. ans = ans%mod;
  60. }
  61. base = base*base;
  62. base %= mod;
  63. exponent>>= 1;
  64. }
  65. return ans%mod;
  66. }
  67. ll modi(ll num)
  68. {
  69. return expo(num,hell-2,hell);
  70. }
  71. void dfs(ll node,ll pr)
  72. {
  73. dp1[node]=1;
  74. ll ans=1;
  75. for(auto i:a[node])
  76. {
  77. if(i!=pr)
  78. {
  79. dfs(i,node);
  80. ans=(ans*modi(fact[dp1[i]]))%hell;
  81. ans=(ans*dp2[i])%hell;
  82. dp1[node]+=dp1[i];
  83. }
  84. }
  85. ans=(ans*fact[dp1[node]-1])%hell;
  86. dp2[node]=ans;
  87. return;
  88. }
  89. void dfs1(ll node,ll pr,ll td2,ll td1)
  90. {
  91. ll ans=(td2*modi(fact[td1]))%hell;
  92. for(auto i:a[node])
  93. {
  94. if(i!=pr)
  95. {
  96. ans=(ans*dp2[i])%hell;
  97. ans=(ans*modi(fact[dp1[i]]))%hell;
  98. }
  99. }
  100. dp3[node]=(ans*fact[n-1])%hell;
  101. ll temp1,temp2;
  102. for(auto i:a[node])
  103. {
  104. if(i!=pr)
  105. {
  106. temp1=(ans*fact[dp1[i]])%hell;
  107. temp1=(temp1*modi(dp2[i]))%hell;
  108. temp2=n-dp1[i];
  109. temp1=(temp1*fact[temp2-1])%hell;
  110. dfs1(i,node,temp1,temp2);
  111. }
  112. }
  113. }
  114. void solve()
  115. {
  116. cin>>n;
  117. fact[0]=1;
  118. rep(i,1,n+1)
  119. fact[i]=(fact[i-1]*i)%hell;
  120. ll x,y;
  121. rep(i,1,n)
  122. {
  123. cin>>x>>y;
  124. a[x].pb(y);
  125. a[y].pb(x);
  126. }
  127. dfs(1,-1);
  128. dfs1(1,-1,1,0);
  129. rep(i,1,n+1)
  130. cout<<dp3[i]<<"\n";
  131. cout<<endl;
  132. return;
  133. }
  134. int main()
  135. {
  136. FAST
  137. int TESTS=1;
  138. // cin>>TESTS;
  139. while(TESTS--)
  140. {
  141. solve();
  142. }
  143. TIME
  144. return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment