rembocoder

Untitled

Apr 11th, 2023
590
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. const int inf = 2e18;
  8. //const int mod = 1e9 + 7;
  9. int mod;
  10.  
  11. vector<vector<int>> g;
  12. vector<int> dp;
  13.  
  14. void count_dp(int v, int p) {
  15.     dp[v] = 1;
  16.     for (int to: g[v]) {
  17.         if (to == p) {
  18.             continue;
  19.         }
  20.         count_dp(to, v);
  21.         (dp[v] *= dp[to] + 1) %= mod;
  22.     }
  23. }
  24.  
  25. vector<int> ans;
  26.  
  27. void reroot(int v, int p, int dp_super) {
  28.     ans[v] = dp[v] * (dp_super + 1) % mod;
  29.     vector<int> sons;
  30.     for (int to: g[v]) {
  31.         if (to == p) {
  32.             continue;
  33.         }
  34.         sons.push_back(to);
  35.     }
  36.     vector<int> pref(sons.size() + 1, 1);
  37.     for (int i = 0; i < sons.size(); i++) {
  38.         pref[i + 1] = pref[i] * (dp[sons[i]] + 1) % mod;
  39.     }
  40.     vector<int> suf(sons.size() + 1, 1);
  41.     for (int i = int(sons.size()) - 1; i >= 0; i--) {
  42.         suf[i] = suf[i + 1] * (dp[sons[i]] + 1) % mod;
  43.     }
  44.     for (int i = 0; i < sons.size(); i++) {
  45.         reroot(sons[i], v, pref[i] * suf[i + 1] % mod * (dp_super + 1) % mod);
  46.     }
  47. }
  48.  
  49. int32_t main() {
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0); cout.tie(0);
  52.     int n;
  53.     cin >> n >> mod;
  54.     g.resize(n);
  55.     for (int i = 0; i < n - 1; i++) {
  56.         int a, b;
  57.         cin >> a >> b;
  58.         a--; b--;
  59.         g[a].push_back(b);
  60.         g[b].push_back(a);
  61.     }
  62.     dp.resize(n);
  63.     count_dp(0, -1);
  64.     ans.resize(n);
  65.     reroot(0, -1, 0);
  66.     for (int x: ans) {
  67.         cout << x << '\n';
  68.     }
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment