SHARE
TWEET

EAGLE1-SPOJ-mr.convict

mr_dot_convict Jun 3rd, 2019 (edited) 30 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. f[v] is len of max path from v in its subtree (just excluding parent) [tree is rooted at 0]
  10. g[v] is len of max path from v using its parent [tree is rooted at 0]
  11. dp[v] = max(f[v], g[v]), length of max path from v [when tree is rooted at 'v']
  12. pref[v][i] = len of max path from v in its subtree (just excluding parent) using 0, ..., i vertices in its adjecency list
  13. suff[v][i] = len of max path from v in its subtree (just excluding parent) using i, ..., deg[v] - 1 vertices in its adjecency list
  14.  
  15. f[u] = max{f[v] + w}
  16. pref[u][i] = max(pref[u][i - 1], f[v] + w)
  17.  suff[u][i] = max(suff[u][i + 1], f[v] + w),  
  18.    g[v] = max(pref[u][i - 1] + w, suff[u][i + 1] + w, g[u] + w)
  19. dp[v] = max(f[v], g[v])
  20.  
  21. where v is children of u (tree rooted at 0), and adj_tree[u][i] = v
  22.  
  23. NOTE : Implementation was simplified by first rooting the tree using rootAt function which removes the parents from adjacency list so pref and suffix are easy to calculate (indexing is difficult otherwise)
  24. */
  25.  
  26. #include         <bits/stdc++.h>
  27. #pragma GCC      optimize ("Ofast")
  28. #pragma GCC      optimize ("unroll-loops")
  29. #pragma GCC      target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  30.  
  31. #define IOS      ios_base::sync_with_stdio(false); cin.tie (nullptr)
  32. #define PREC     cout.precision (10); cout << fixed
  33. #define x        first
  34. #define y        second
  35. using namespace std;
  36. using pii = pair <int, long long>;
  37.  
  38. const int N = (int) 1e5 + 10;
  39. int V, n;
  40. vector < vector <pii> > Adj;
  41. long long f[N], g[N], dp[N];
  42. vector < vector <long long> > pref, suff;
  43.  
  44. void read() {
  45.     cin >> n;
  46.     V = n;
  47.     Adj.assign(n, vector <pii>());
  48.     pref.assign(n, vector <long long>());
  49.     suff.assign(n, vector <long long>());
  50.     int u, v;
  51.     long long w;
  52.     for (int e = 0; e < n - 1; ++e) {
  53.         cin >> u >> v >> w;
  54.         --u, --v;
  55.         Adj[u].emplace_back(pii(v, w));
  56.         Adj[v].emplace_back(pii(u, w));
  57.     }
  58.  
  59.     for (int i = 0; i < n; ++i) {
  60.         dp[i] = g[i] = f[i] = 0;
  61.     }
  62. }
  63.  
  64. void rootAt (int u, int pr) {
  65.     for (int i = 0; i < (int) Adj[u].size(); ++i) {
  66.         int v = Adj[u][i].x;
  67.         if (v == pr)
  68.             Adj[u].erase (Adj[u].begin() + i);
  69.     }
  70.  
  71.     for (int i = 0; i < (int) Adj[u].size(); ++i) {
  72.         int v = Adj[u][i].x;
  73.         rootAt(v, u);
  74.     }
  75. }
  76.  
  77. void dfsF (int u) {
  78.     for (auto vPair : Adj[u]) {
  79.         int v = vPair.x;
  80.         dfsF (v);
  81.     }
  82.  
  83.     long long fval = 0;
  84.     for (auto vPair : Adj[u]) {
  85.         int v = vPair.x;
  86.         long long w = vPair.y;
  87.         fval = max(fval, f[v] + w);
  88.     }
  89.     f[u] = fval;
  90.  
  91.     int sz = (int) Adj[u].size();
  92.     if (sz != 0) {
  93.         pref[u].assign(sz, 0);
  94.         suff[u].assign(sz, 0);
  95.  
  96.         for (int i = 0; i < sz; ++i) {
  97.             int v = Adj[u][i].x;
  98.             long long w = Adj[u][i].y;
  99.             if (i == 0) pref[u][i] = f[v] + w;
  100.             else pref[u][i] = max(pref[u][i - 1], f[v] + w);
  101.         }
  102.  
  103.         for (int i = sz - 1; i >= 0; --i) {
  104.             int v = Adj[u][i].x;
  105.             long long w = Adj[u][i].y;
  106.             if (i == sz - 1) suff[u][i] = f[v] + w;
  107.             else suff[u][i] = max(suff[u][i + 1], f[v] + w);
  108.         }
  109.     }
  110. }
  111.  
  112. void dfsG (int u, int pr) {
  113.     if (pr == -1) g[u] = 0;
  114.     int sz = (int) Adj[u].size();
  115.  
  116.     for (int i = 0; i < sz; ++i) {
  117.         long long gval = 0;
  118.         int v = Adj[u][i].x;
  119.         long long w = Adj[u][i].y;
  120.         if (i != 0) {
  121.             gval = max (gval, pref[u][i - 1] + w);
  122.         }
  123.         if (i != sz - 1) {
  124.             gval = max (gval, suff[u][i + 1] + w);
  125.         }
  126.         gval = max (gval, g[u] + w);
  127.         g[v] = gval;
  128.     }
  129.  
  130.     dp[u] = max (f[u], g[u]);
  131.  
  132.     for (auto vPair : Adj[u]) {
  133.         int v = vPair.x;
  134.         dfsG (v, u);
  135.     }
  136. }
  137.  
  138. void solve () {
  139.     for (int v = 0; v < n; ++v) cout << dp[v] << ' ';
  140.     cout << '\n';
  141. }
  142.  
  143. signed main() {
  144.     IOS; PREC;
  145.     int tc;
  146.     cin >> tc;
  147.     while (tc--) {
  148.         read();
  149.         rootAt(0, -1);
  150.         dfsF(0);
  151.         dfsG(0, -1);
  152.         solve();
  153.     }
  154.  
  155.     return EXIT_SUCCESS;
  156. }
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
 
Top