This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// punch then pray
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)1e5 ;
const int maxN = (int)5e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
const int block_size = 710;
void InputFile()
{
//freopen("palpath.in","r",stdin);
//freopen("palpath.out","w",stdout);
//freopen("test.inp","r",stdin);
//freopen("test.out","w",stdout);
}
void FastInput()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
/// combining subtree nhung chi dua vao la ?
/// n log cho moi goc ?
/// n ^ 2 log full goc ?
int n,k;
vector<vector<pii>> adj;
int x[2005],y[2005],c[2005];
ll dp[2005][2005];
ll f[2005];
int subleaf[2005];
void Read()
{
cin >> n >> k;
adj.resize(n+1);
for(int i = 1;i < n;i++)
{
cin >> x[i] >> y[i] >> c[i];
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
}
void PreDFS(int u,int p)
{
subleaf[u] = 1;
int non_leaf = 0;
for(pii e : adj[u])
{
int v = e.fi;
int wt = e.se;
if(v == p) continue;
PreDFS(v,u);
non_leaf = 1;
subleaf[u] += subleaf[v];
}
subleaf[u] -= non_leaf;
}
void DFS(int u,int p)
{
int sleaf = 0;
for(pii e : adj[u])
{
int v = e.fi;
int wt = e.se;
if(v == p) continue;
DFS(v,u);
for(int i = 1;i <= min(k,sleaf + subleaf[v]);i++)
{
f[i] = 0;
}
for(int i = 0;i <= sleaf;i++)
{
f[i] = max(f[i],dp[u][i]);
for(int j = 1;j <= min(subleaf[v],k);j++)
{
if(i + j > k) break;
f[i+j] = max(f[i+j],dp[u][i] + dp[v][j] + wt);
}
}
for(int i = 1;i <= min(k,sleaf + subleaf[v]);i++)
{
dp[u][i] = f[i];
}
sleaf += subleaf[v];
sleaf = min(sleaf,k);
}
}
void Prc_root(int id)
{
PreDFS(id,0);
DFS(id,0);
ll res = 0;
for(int i = 1;i <= n;i++)
{
//cout << subleaf[i] <<' ';
for(int j = 1;j <= subleaf[i];j++)
{
res = max(res,dp[i][j]);
dp[i][j] = 0;
}
}
//cout << dp[7][2];
cout << res <<'\n';
}
void Solve()
{
for(int i = 1;i <= n;i++)
{
Prc_root(i);
}
//Prc_root(1);
}
int32_t main()
{
FastInput();
//InputFile();
//int sub_type;
//cin >> sub_type;
//Sieve()
int test;
//cin >> test;
test = 1;
while(test--)
{
Read();
Solve();
//Debug();
}
}
////
/////
//////
Compilation message (stderr)
Main.cpp: In function 'void PreDFS(int, int)':
Main.cpp:68:13: warning: unused variable 'wt' [-Wunused-variable]
68 | int wt = e.se;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |