sacgajcvs

Untitled

Mar 31st, 2020
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.76 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 100005
  50. ll n,m;
  51. vi a[N];
  52. ll dp1[N],dp2[N];
  53.  
  54. void dfs(ll node,ll pr)
  55. {
  56. dp1[node]=1;
  57. for(auto i:a[node])
  58. {
  59. if(i!=pr)
  60. {
  61. dfs(i,node);
  62. dp1[node]=(dp1[node]*(dp1[i]+1))%m;
  63. }
  64. }
  65. return;
  66. }
  67. void dfs1(ll node,ll pr,ll pre)
  68. {
  69. vi v1,v2;
  70.  
  71. v1.pb(1);
  72. for(auto i:a[node])
  73. {
  74. if(i==pr)
  75. {
  76. v1.pb(1);
  77. v2.pb(1);
  78. }
  79. else
  80. {
  81. v1.pb(dp1[i]+1);
  82. v2.pb(dp1[i]+1);
  83. }
  84. }
  85. v2.pb(1);
  86.  
  87. ll temp_n=sz(a[node]);
  88.  
  89. rep(i,1,temp_n+1)
  90. v1[i]=(v1[i]*v1[i-1])%m;
  91.  
  92. repr(i,0,temp_n)
  93. v2[i]=(v2[i]*v2[i+1])%m;
  94.  
  95. ll num;
  96. rep(i,0,temp_n)
  97. {
  98. if(a[node][i]==pr)
  99. continue;
  100.  
  101. num=(v1[i]*v2[i+1])%m;
  102.  
  103. dfs1(a[node][i],node,(num*(pre+1))%m);
  104. }
  105. dp2[node]=(v1[temp_n]*(pre+1))%m;
  106. return;
  107. }
  108.  
  109. void solve()
  110. {
  111. cin>>n>>m;
  112. ll x,y;
  113. rep(i,1,n)
  114. {
  115. cin>>x>>y;
  116. a[x].pb(y);
  117. a[y].pb(x);
  118. }
  119. dfs(1,-1);
  120. dfs1(1,-1,0);
  121. rep(i,1,n+1)
  122. {
  123. cout<<dp2[i]<<"\n";
  124. }
  125. return;
  126. }
  127. int main()
  128. {
  129. FAST
  130. int TESTS=1;
  131. // cin>>TESTS;
  132. while(TESTS--)
  133. {
  134. solve();
  135. }
  136. TIME
  137. return 0;
  138. }
Advertisement
Add Comment
Please, Sign In to add comment