Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Make CSP great again
- //Vengeance
- #include <bits/stdc++.h>
- #define TASK "TESTCODE"
- #define Log2(x) 31 - __builtin_clz(x)
- using namespace std;
- const int N = 1e5;
- vector<pair<int, int> > adj[N + 1];
- int n, k;
- long long dp[N + 1], g[N + 1], res[N + 1], val = 0;
- multiset<long long> in, out;
- void add(long long a)
- {
- val += a;
- in.insert(a);
- if (in.size() > k)
- {
- val -= *in.begin();
- out.insert(*in.begin());
- in.erase(in.begin());
- }
- }
- void del(long long a)
- {
- auto it = out.find(a);
- if (it != out.end())
- {
- out.erase(it);
- return ;
- }
- it = in.find(a);
- assert(it != in.end());
- val -= a;
- in.erase(it);
- if (!out.empty())
- {
- val += *out.rbegin();
- in.insert(*out.rbegin());
- it = out.end();
- --it;
- out.erase(it);
- }
- }
- void DFS_down(int u, int p)
- {
- for (auto &x : adj[u])
- {
- if (x.first == p)
- {
- continue;
- }
- DFS_down(x.first, u);
- dp[u] = max(dp[u], dp[x.first] + x.second);
- }
- }
- void DFS_up(int u, int p)
- {
- long long s[2], f[2];
- s[0] = s[1] = -1;
- f[0] = f[1] = 0;
- for (auto &x : adj[u])
- {
- int v = x.first, w = x.second;
- if (v == p)
- {
- continue;
- }
- for (int i = 1; i >= 0; -- i)
- {
- if (dp[v] + w > f[i])
- {
- for (int j = 0; j < i; ++ j)
- {
- f[j] = f[j + 1];
- s[j] = s[j + 1];
- }
- f[i] = dp[v] + w;
- s[i] = v;
- break;
- }
- }
- }
- for (auto &x : adj[u])
- {
- int v = x.first, w = x.second;
- if (v == p)
- {
- continue;
- }
- g[v] = g[u];
- for (int i = 1; i >= 0; -- i)
- {
- if (s[i] != v)
- {
- g[v] = max(g[v], f[i]);
- break;
- }
- }
- g[v] += w;
- DFS_up(v, u);
- if (v != s[1])
- {
- add(dp[v] + w);
- }
- }
- //cerr << u << ' ' << dp[u] << ' ' << g[u] << '\n';
- }
- void DFS(int u, int p)
- {
- res[u] = val;
- for (auto &x : adj[u])
- {
- int v = x.first, w = x.second;
- if (v == p)
- {
- continue;
- }
- add(dp[v]);
- del(dp[v] + w);
- add(g[v]);
- del(g[v] - w);
- DFS(v, u);
- del(dp[v]);
- add(dp[v] + w);
- del(g[v]);
- add(g[v] - w);
- }
- }
- void read()
- {
- cin >> n >> k;
- for (int i = 1; i < n; ++ i)
- {
- int u, v, w;
- cin >> u >> v >> w;
- adj[u].push_back({v, w});
- adj[v].push_back({u, w});
- }
- }
- void solve()
- {
- DFS_down(1, 0);
- DFS_up(1, 0);
- add(dp[1]);
- add(0);
- DFS(1, 0);
- for (int u = 1; u <= n; ++ u)
- {
- cout << res[u] << '\n';
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- if (fopen(TASK".INP", "r"))
- {
- freopen(TASK".INP", "r", stdin);
- //freopen(TASK".OUT", "w", stdout);
- }
- int t = 1;
- bool typetest = false;
- if (typetest)
- {
- cin >> t;
- }
- for (int __ = 1; __ <= t; ++ __)
- {
- //cout << "Case " << __ << ": ";
- read();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement