SHARE
TWEET

543-D-Road-Improvement-Codeforces-mr.convict

mr_dot_convict May 27th, 2019 (edited) 29 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*author* Priyanshu Shrivastav (from IIT Palakkad) *
  2.  * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
  3.  * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
  4.  * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
  5.  * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
  6. When I wrote this, only God and I understood what I was doing
  7.  ** * * * * * * * Now, only God knows * * * * * * */
  8. /*
  9. Similar to EAGLE1 SPOJ (https://pastebin.com/vq9vRG2E, here is an explanation and code for it), just change the recursion
  10.         f[u] = mul(fval, 1 + f[v])
  11. pref[u][i] = mul(pref[u][i - 1], (1 + f[v]))
  12. suff[u][i] = mul(suff[u][i + 1], (1 + f[v]))
  13.    g[v] = mul(pref[u][i - 1] + w, suff[u][i + 1] + w, g[u] + w) + 1
  14.  dp[v] = mul(f[v], g[v])
  15. */
  16. #include         <bits/stdc++.h>
  17. #pragma GCC      optimize ("unroll-loops")
  18. #pragma GCC      target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  19.  
  20. #define IOS      ios_base::sync_with_stdio(false); cin.tie (nullptr)
  21. #define PREC     cout.precision (10); cout << fixed
  22. #define x        first
  23. #define y        second
  24.  
  25. using namespace std;
  26.  
  27. /*HackItAndHaveIt*/
  28.  
  29. const int N = (int) 2e5 + 10;
  30. const int Mod = (int) 1e9 + 7;
  31.  
  32. int n, V;
  33. vector <vector <int> > Adj;
  34. long long f[N], g[N], dp[N];
  35. vector < vector <long long> > pref, suff;
  36.  
  37. long long mul (long long a, long long b) {
  38.     a *= b;
  39.     a %= Mod;
  40.     return a;
  41. }
  42.  
  43. void read() {
  44.     cin >> n;
  45.     Adj.assign(n, vector <int>());
  46.     pref.assign(n, vector <long long> ());
  47.     suff.assign(n, vector <long long> ());
  48.  
  49.     for (int i = 1; i < n; ++i) {
  50.         int u = i, v;
  51.         cin >> v; --v;
  52.         Adj[u].emplace_back(v);
  53.         Adj[v].emplace_back(u);
  54.     }
  55.     for (int i = 0; i < n; ++i)
  56.         dp[i] = f[i] = g[i] = 0;
  57. }
  58.  
  59. void rootAt (int u, int pr) {
  60.     for (int i = 0; i < (int) Adj[u].size(); ++i) {
  61.         int v = Adj[u][i];
  62.         if (v == pr)
  63.             Adj[u].erase (Adj[u].begin() + i);
  64.     }
  65.     for (int i = 0; i < (int) Adj[u].size(); ++i) {
  66.         int v = Adj[u][i];
  67.         rootAt (v, u);
  68.     }
  69. }
  70.  
  71. void dfsF(int u) {
  72.     for (auto v : Adj[u])
  73.         dfsF (v);
  74.  
  75.     long long fval = 1;
  76.     for (int i = 0; i < (int) Adj[u].size(); ++i) {
  77.         int v = Adj[u][i];
  78.         fval = mul(fval, 1 + f[v]);
  79.     }
  80.     f[u] = fval;
  81.  
  82.     pref[u].assign((int)Adj[u].size(), 0);
  83.     suff[u].assign((int)Adj[u].size(), 0);
  84.  
  85.     for (int i = 0; i < (int)Adj[u].size(); ++i) {
  86.         int v = Adj[u][i];
  87.         if (i == 0)
  88.             pref[u][i] = 1 + f[v];
  89.         else pref[u][i] = mul (pref[u][i - 1], (1 + f[v]));
  90.     }
  91.  
  92.     for (int i = (int)Adj[u].size() - 1; i >= 0; --i) {
  93.         int v = Adj[u][i];
  94.         if (i == (int)Adj[u].size() - 1)
  95.             suff[u][i] = 1 + f[v];
  96.         else suff[u][i] = mul (suff[u][i + 1], (1 + f[v]));
  97.     }
  98. }
  99.  
  100. void dfsG(int u, int pr) {
  101.     if (pr == -1) g[u] = 1;
  102.  
  103.     for (int i = 0; i < (int) Adj[u].size(); ++i) {
  104.         int v = Adj[u][i];
  105.         long long gval = 1;
  106.         if (i != 0)
  107.             gval = mul (gval, pref[u][i - 1]);
  108.         if (i != (int) Adj[u].size() - 1)
  109.             gval = mul (gval, suff[u][i + 1]);
  110.         gval = mul (gval, g[u]);
  111.         g[v] = gval + 1;
  112.     }
  113.  
  114.     dp[u] = (f[u] * g[u]) % Mod;
  115.  
  116.     for (auto v : Adj[u])
  117.         dfsG (v, u);
  118. }
  119.  
  120. void solve() {
  121.     for (int v = 0; v < n; ++v)
  122.         cout << dp[v] << ' ';
  123.     cout << '\n';
  124. }
  125.  
  126. signed main() {
  127.     IOS; PREC;
  128.     read();
  129.     rootAt(0, -1);
  130.     dfsF(0);
  131.     dfsG(0, -1);
  132.     solve();
  133.     return EXIT_SUCCESS;
  134. }
RAW Paste Data
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top