#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int inf = 1e18;
const int mod = 1e9 + 7;
//struct bitt {
//vector<int> t;
//int n;
//bitt (int N) : n(N+1) {
//t.resize(n+2);
//};
//void upd(int i, int va) { i ++ ;
//for(; i < n; i += (i & -i)) t[i] += va;
//};
//int get(int i) { i ++ ;
//int res = 0;
//for(; i > 0; i -= (i & -i)) res += t[i];
//return res;
//};
//int get(int l, int r) { r--;
//return get(r ) - get( -- l );
//};
//};
void solve(){
int n, k;
cin >> n >> k;
vector<vector<array<int,2>>> g(n+1);
for(int i = 1; i < n; i ++ ) {
int a, b, c; cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
};
vector<vector<int> > dp(n+1, vector<int> (min(k+1, n+1), 0));
function<void(int, int) > dfs = [&](int ps, int pr) {
for(auto [to, c] : g[ps]){
if(to == pr)continue;
dfs(to, ps);
for(int j = dp[ps].size(); j >= 0; j -- ) {
for(int i = 1; i+j < dp[ps].size(); i ++ ) {
dp[ps][j+i] = max(dp[ps][j+i], dp[ps][j] + dp[to][i] + c);
}
}
}
//cout << ps << '\n';
//for(int i = 0; i < dp[ps].size(); i ++ ) {
//cout << dp[ps][i] << ' ';
//}
//cout << '\n';
};
//dfs(1, 1);
for(int i = 1; i <= n; i ++ ) {
dfs(i, i);
cout << dp[i][k] << '\n';
for(auto &i : dp)
for(auto &j : i)j = 0;
};
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt -- ){
solve();
};
};
# | 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... |