mr_dot_convict

EAGLE1-SPOJ-mr.convict

Jun 3rd, 2019
198
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