#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)
#define N 200005
#define ALL(x) x.begin(), x.end()
int n, k;
vector<pair<int, int>> g[N];
namespace sub123
{
ll dp[1001][101];
int sz[N];
void dfs1(int u, int p)
{
dp[u][0] = dp[u][1] = 0;
sz[u] = 1;
for (auto [w, v] : g[u]) if (v != p)
{
dfs1(v, u);
for (int i = sz[u]; i >= 0; --i)
for (int j = 1; i+j <= k && j <= sz[v]; ++j)
dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[v][j] + w);
sz[u] += sz[v];
}
}
ll oneroot(int u)
{
memset(dp, 0xbf, sizeof dp);
dfs1(u, u);
return dp[u][k];
}
};
namespace sub5
{
ll dp2[N], dp3[N], dp4[N];
void dfs2(int u, int p)
{
dp2[u] = 0;
for (auto [w, v] : g[u]) if (v != p)
{
dfs2(v, u);
if (dp2[v] + w >= dp2[u]) dp3[u] = dp2[u], dp2[u] = dp2[v] + w;
else if (dp2[v] + w >= dp3[u]) dp3[u] = dp2[v] + w;
}
}
void dfs3(int u, int p)
{
for (auto [w, v] : g[u]) if (v != p)
{
if (dp2[v] + w == dp2[u]) dp4[v] = max(dp4[u] + w, dp3[u] + w);
else dp4[v] = max(dp4[u] + w, dp2[u] + w);
dfs3(v, u);
}
}
};
namespace sub4
{
int tin[2001], tout[2001], timer, P[2001][2], rv[2001];
ll rt[N]{0};
struct segtree
{
pair<ll, int> t[4005]; ll lz[4005]{0};
segtree() { }
void build(int v, int l, int r)
{
if (l >= r) {
int u = rv[l];
lz[v]=0;
if (tin[u]==tout[u]) t[v] = {rt[u], u};
else t[v] = {-1e17,u};
return;
}
int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
build(vl,l,m),build(vr,m+1,r);
t[v]=max(t[vl],t[vr]);
}
void push(int v, int l, int r)
{
if (!lz[v])return;
if (t[v].first>-1e17)t[v].first+=lz[v];
if(l-r)
{
int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
lz[vl]+=lz[v];lz[vr]+=lz[v];
}
lz[v]=0;
}
pair<ll, int> qry(int x, int y, int v, int l, int r)
{
push(v,l,r);
if (y<l||r<x) return {-1e18, -1e9};
if (x<=l&&r<=y){return t[v];}
int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
return max(qry(x, y, vl,l,m),qry(x,y,vr,m+1,r));
}
void upd(int x, int y, int k, int v, int l, int r)
{
push(v,l,r);
if (y<l||r<x) return;
if (x<=l&&r<=y){lz[v]=k;push(v,l,r);return;}
int m = (l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
upd(x, y,k,vl,l,m),upd(x,y,k,vr,m+1,r);
t[v]=max(t[vl],t[vr]);
}
} t;
void dfs1(int u, int p)
{
rv[tin[u] = timer++] = u;
for (auto [w, v] : g[u]) if (v-p) P[v][0]=u,P[v][1]=w,rt[v]=rt[u]+w,dfs1(v, u);
tout[u] = timer - 1;
}
ll ans;
int del[2010]{0};
void process()
{
pair<ll,int> x = t.qry(0,n-1,0,0,n-1);
ans += x.first;
for (int c = x.second; c; c = P[c][0])
{
int p = P[c][0], w = P[c][1];
if(!del[c])
t.upd(tin[c], tout[c], -w, 0, 0, n-1),del[c]=1;
}
}
ll oneroot(int root)
{
memset(rt,0,sizeof rt);
memset(del,0,sizeof del);
memset(P,0,sizeof P);
rt[root]=ans=timer=0;
dfs1(root,root);
t.build(0,0,n-1);
for (int i = 1; i <= k; ++i) process();
return ans;
}
};
int main()
{
ShinLena;
cin >> n >> k;
for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
if (k == 1)
{
sub5::dfs2(1, 1);
sub5::dfs3(1, 1);
for (int i = 1; i <= n; ++i) cout << max(sub5::dp2[i], sub5::dp4[i]) << '\n';
}
else if (n <= 2000)
{
for (int i = 1; i <= n; ++i) cout << sub4::oneroot(i) << '\n';
}
else if (n <= 1002)
{
for (int i = 1; i <= n; ++i) cout << sub123::oneroot(i) << '\n';
}
else
{
}
return 0;
}
Compilation message
Main.cpp: In function 'void sub4::process()':
Main.cpp:147:17: warning: unused variable 'p' [-Wunused-variable]
147 | int p = P[c][0], w = P[c][1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
16336 KB |
Output is correct |
| 2 |
Correct |
71 ms |
17760 KB |
Output is correct |
| 3 |
Correct |
50 ms |
15840 KB |
Output is correct |
| 4 |
Correct |
53 ms |
16216 KB |
Output is correct |
| 5 |
Correct |
50 ms |
16928 KB |
Output is correct |
| 6 |
Correct |
57 ms |
16264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
