#include <bits/stdc++.h> using namespace std; #define int long long #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() const int N = 1e5 + 7; const int inf = 1e18 + 7; struct SEGT{ vector < pair<int,int> > t; int tree_size; const pair<int,int> identity_element = {-inf,-inf};// value , index pair<int,int> merge(pair<int,int> &x , pair<int,int> &y){ return max(x,y); } void init(int x){ tree_size = x+3; t.assign(2*tree_size , identity_element); } void modify(int p, pair<int,int> value) { // set value at position p for (t[p += tree_size] = value; p > 1; p >>= 1){ t[p>>1] = merge(t[p] , t[p^1]); } } pair<int,int> query(int l, int r) { // sum on interval [l, r] pair<int,int> res = identity_element; for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) { if (l&1) res = merge(res , t[l++]); if (r&1) res = merge(res , t[--r]); } return res; } } segt; int n,k; int ans[N]; vector<pair<int,int>>tree[N]; int heavy[N]; int set_heavy(int node , int par){ int maxi = -1; for(auto itr : tree[node]){ if(itr.first == par)continue; int val = set_heavy(itr.first , node) + itr.second; if(maxi < val){ heavy[node] = itr.first; maxi = val; } } if(maxi == -1)heavy[node] = -1; return maxi == -1 ? 0ll : maxi; } vector<pair<int , int>>leafs;// path cevabi , node int mini[N] , maxi[N]; void retrieve(int node , int par , int cumans){ if(heavy[node] == -1){ mini[node] = maxi[node] = sz(leafs); // cout << "MINI/MAXI " << node+1 << " : " << mini[node] << " " << maxi[node] << endl; leafs.push_back({cumans , node}); return; } mini[node] = -1; for(auto itr : tree[node]){ if(itr.first == par)continue; if(heavy[node] == itr.first){ retrieve(itr.first , node , cumans + itr.second); } else{ retrieve(itr.first , node , itr.second); } if(mini[node] == -1)mini[node] = mini[itr.first]; maxi[node] = maxi[itr.first]; } // cout << "MINI/MAXI " << node+1 << " : " << mini[node] << " " << maxi[node] << endl; } multiset<int>ste1 , ste2; int sum1 = 0; void rebalance(){ while(sz(ste1) > k){ sum1 -= *ste1.begin(); ste2.insert(*ste1.begin()); ste1.erase(ste1.begin()); } while(sz(ste1) < k and !ste2.empty()){ sum1 += *--ste2.end(); ste1.insert(*--ste2.end()); ste2.erase(--ste2.end()); } while(!ste1.empty() and !ste2.empty() and *ste1.begin() < *--ste2.end()){ int tmp1 = *ste1.begin() , tmp2 = *--ste2.end(); sum1 -= tmp1; ste1.erase(ste1.begin()); ste2.erase(--ste2.end()); sum1 += tmp2; ste1.insert(tmp2); ste2.insert(tmp1); } } void add(int x){ ste2.insert(x); rebalance(); } void del(int x){ if(ste2.count(x)){ ste2.erase(ste2.find(x)); } else if(ste1.count(x)){ sum1 -= x; ste1.erase(ste1.find(x)); } else assert(false); rebalance(); } pair<int,int> MAX(pair<int,int> A , pair<int,int> B){ if(A > B)return A; return B; } void dfs(int node , int par){ ans[node] = sum1; // cout << "DFS : " << node+1 << " , " << ans[node] << endl; // cout << "leafs : ";for(auto itr : leafs)cout << itr.second+1 << " ";cout << endl; // cout << "SEGT : ";for(int i = 0;i<sz(leafs);i++)cout << segt.query(i,i).first << " ";cout << endl; // cout << "ste1 : ";for(auto itr : ste1)cout << itr << " ";cout << endl; // cout << "ste2 : ";for(auto itr : ste2)cout << itr << " ";cout << endl; // cout << endl; for(auto itr : tree[node]){ if(itr.first == par)continue; // cout << node+1 << " -> " << itr.first+1 << " : " << mini[itr.first] << " " << maxi[itr.first] << endl; auto tmp1 = segt.query(mini[itr.first] , maxi[itr.first]); del(tmp1.first); segt.modify(tmp1.second , {tmp1.first - itr.second , tmp1.second}); add(tmp1.first - itr.second); auto tmp2 = pair<int,int>{-inf,-inf}; if(mini[itr.first] != 0){ tmp2 = MAX(tmp2 , segt.query(0 , mini[itr.first]-1)); } if(maxi[itr.first] != sz(leafs)-1){ tmp2 = MAX(tmp2 , segt.query(maxi[itr.first]+1 , sz(leafs)-1)); } if(tmp2 != pair<int,int>{-inf,-inf}){ del(tmp2.first); segt.modify(tmp2.second , {tmp2.first + itr.second , tmp2.second}); add(tmp2.first + itr.second); } dfs(itr.first , node); if(tmp2 != pair<int,int>{-inf,-inf}){ del(tmp2.first + itr.second); segt.modify(tmp2.second , tmp2); add(tmp2.first); } del(tmp1.first - itr.second); segt.modify(tmp1.second , tmp1); add(tmp1.first); } } void solve(){ cin >> n >> k; for(int i = 1;i<n;i++){ int x,y,c; cin >> x >> y >> c; x-- , y--; tree[x].push_back({y , c}); tree[y].push_back({x , c}); } set_heavy(0 , 0); retrieve(0 , 0 , 0ll); segt.init(sz(leafs)); for(int i = 0;i<sz(leafs);i++){ segt.modify(i , {leafs[i].first , i}); add(leafs[i].first); } // cout << "leafs : ";for(auto itr : leafs)cout << itr.first << "," << itr.second+1 << " ";cout << endl; dfs(0,0); for(int i = 0;i<n;i++){ cout << ans[i] << '\n'; } cout << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase=1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }