Advertisement
tien_noob

RMI21 - Paths (DP reroot - hard)

May 26th, 2022
621
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Make CSP great again
  2. //Vengeance
  3. #include <bits/stdc++.h>
  4. #define TASK "TESTCODE"
  5. #define Log2(x) 31 - __builtin_clz(x)
  6. using namespace std;
  7. const int N = 1e5;
  8. vector<pair<int, int> > adj[N + 1];
  9. int n, k;
  10. long long dp[N + 1], g[N + 1], res[N + 1], val = 0;
  11. multiset<long long> in, out;
  12. void add(long long a)
  13. {
  14.     val += a;
  15.     in.insert(a);
  16.     if (in.size() > k)
  17.     {
  18.         val -= *in.begin();
  19.         out.insert(*in.begin());
  20.         in.erase(in.begin());
  21.     }
  22. }
  23. void del(long long a)
  24. {
  25.     auto it = out.find(a);
  26.     if (it != out.end())
  27.     {
  28.         out.erase(it);
  29.         return ;
  30.     }
  31.     it = in.find(a);
  32.     assert(it != in.end());
  33.     val -= a;
  34.     in.erase(it);
  35.     if (!out.empty())
  36.     {
  37.         val += *out.rbegin();
  38.         in.insert(*out.rbegin());
  39.         it = out.end();
  40.         --it;
  41.         out.erase(it);
  42.     }
  43. }
  44. void DFS_down(int u, int p)
  45. {
  46.     for (auto &x : adj[u])
  47.     {
  48.         if (x.first == p)
  49.         {
  50.             continue;
  51.         }
  52.         DFS_down(x.first, u);
  53.         dp[u] = max(dp[u], dp[x.first] + x.second);
  54.     }
  55. }
  56. void DFS_up(int u, int p)
  57. {
  58.     long long s[2], f[2];
  59.     s[0] = s[1] = -1;
  60.     f[0] = f[1] = 0;
  61.     for (auto &x : adj[u])
  62.     {
  63.         int v = x.first, w = x.second;
  64.         if (v == p)
  65.         {
  66.             continue;
  67.         }
  68.         for (int i = 1; i >= 0; -- i)
  69.         {
  70.             if (dp[v] + w > f[i])
  71.             {
  72.                 for (int j = 0; j < i; ++ j)
  73.                 {
  74.                     f[j] = f[j + 1];
  75.                     s[j] = s[j + 1];
  76.                 }
  77.                 f[i] = dp[v] + w;
  78.                 s[i] = v;
  79.                 break;
  80.             }
  81.         }
  82.     }
  83.     for (auto &x : adj[u])
  84.     {
  85.         int v = x.first, w = x.second;
  86.         if (v == p)
  87.         {
  88.             continue;
  89.         }
  90.         g[v] = g[u];
  91.         for (int i = 1; i >= 0; -- i)
  92.         {
  93.             if (s[i] != v)
  94.             {
  95.                 g[v] = max(g[v], f[i]);
  96.                 break;
  97.             }
  98.         }
  99.         g[v] += w;
  100.         DFS_up(v, u);
  101.         if (v != s[1])
  102.         {
  103.             add(dp[v] + w);
  104.         }
  105.     }
  106.     //cerr << u << ' ' << dp[u] << ' ' << g[u] << '\n';
  107. }
  108. void DFS(int u, int p)
  109. {
  110.     res[u] = val;
  111.     for (auto &x : adj[u])
  112.     {
  113.         int v = x.first, w = x.second;
  114.         if (v == p)
  115.         {
  116.             continue;
  117.         }
  118.         add(dp[v]);
  119.         del(dp[v] + w);
  120.         add(g[v]);
  121.         del(g[v] - w);
  122.         DFS(v, u);
  123.         del(dp[v]);
  124.         add(dp[v] + w);
  125.         del(g[v]);
  126.         add(g[v] - w);
  127.     }
  128. }
  129. void read()
  130. {
  131.     cin >> n >> k;
  132.     for (int i = 1; i < n; ++ i)
  133.     {
  134.         int u, v, w;
  135.         cin >> u >> v >> w;
  136.         adj[u].push_back({v, w});
  137.         adj[v].push_back({u, w});
  138.     }
  139. }
  140. void solve()
  141. {
  142.     DFS_down(1, 0);
  143.     DFS_up(1, 0);
  144.     add(dp[1]);
  145.     add(0);
  146.     DFS(1, 0);
  147.     for (int u = 1; u <= n; ++ u)
  148.     {
  149.         cout << res[u] << '\n';
  150.     }
  151. }
  152. int main()
  153. {
  154.     ios_base::sync_with_stdio(false);
  155.     cin.tie(nullptr);
  156.     if (fopen(TASK".INP", "r"))
  157.     {
  158.         freopen(TASK".INP", "r", stdin);
  159.         //freopen(TASK".OUT", "w", stdout);
  160.     }
  161.     int t = 1;
  162.     bool typetest = false;
  163.     if (typetest)
  164.     {
  165.         cin >> t;
  166.     }
  167.     for (int __ = 1; __ <= t; ++ __)
  168.     {
  169.         //cout << "Case " << __ << ": ";
  170.         read();
  171.         solve();
  172.     }
  173. }
  174.  
Advertisement
RAW Paste Data Copied
Advertisement