#include "roads.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 100005;
lint dp[MAXN];
int par[MAXN], pae[MAXN];
vector<pi> gph[MAXN];
vector<int> dfn;
void dfs(int x, int p = -1){
dfn.push_back(x);
for(auto &[w, y] : gph[x]){
pae[y] = w;
par[y] = x;
gph[y].erase(find(all(gph[y]), pi(w, x)));
dfs(y, x);
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
for(int i = 0; i < N - 1; i++){
gph[U[i]].emplace_back(W[i], V[i]);
gph[V[i]].emplace_back(W[i], U[i]);
}
dfs(0);
vector<lint> ans(N);
reverse(all(dfn));
ans[0] = accumulate(all(W), 0ll);
for(int k = N - 1; k > 0; k--){
for(auto &j : dfn){
vector<lint> v;
for(auto &[w, s] : gph[j]){
ans[k] += w;
v.push_back(dp[s]);
}
sort(all(v));
for(int j = 0; j < min(sz(v), k); j++) ans[k] += v[j];
dp[j] = min(0ll, -(sz(v) >= k ? v[k-1] : 0) - pae[j]);
}
}
return ans;
}
/*#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<int, int>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 100005;
vector<pi> gph[MAXN];
vector<int> ord;
int par[MAXN], pae[MAXN];
void dfs(int x, int p = -1){
ord.push_back(x);
for(auto &[w, v] : gph[x]){
gph[v].erase(find(all(gph[v]), pi(w, x)));
if(v != p){
par[v] = x;
pae[v] = w;
dfs(v, x);
}
}
}
lint dp[MAXN];
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
for(int i = 0; i < N-1; i++){
gph[U[i]].emplace_back(W[i], V[i]);
gph[V[i]].emplace_back(W[i], U[i]);
}
dfs(0);
vector<lint> ans(N);
vector<multiset<lint>> vect(N);
reverse(all(ord));
ans[0] = accumulate(pae, pae + N, 0ll);
for(auto &v : ord){
for(int q = 0; q < sz(gph[v]); q++) vect[v].insert(0);
}
auto getsum = [&](multiset<lint> &ms, int k){
lint ret = 0;
auto it = ms.begin();
while(k-- && it != ms.end()){
ret += min(*it, 0ll);
it++;
}
return ret;
};
auto getkth = [&](multiset<lint> &ms, int k){
return getsum(ms, k) - getsum(ms, k-1);
};
ans[0] = accumulate(pae, pae + N, 0ll);
lint ret = 0;
for(int i = N-1; i >= 1; i--){
for(auto &v : ord){
if(sz(gph[v]) <= i) continue;
ret -= getkth(vect[v], i);
ret -= getsum(vect[par[v]], i);
ret += dp[v];
if(v) vect[par[v]].erase(vect[par[v]].find(dp[v]));
dp[v] = 0;
dp[v] -= pae[v];
dp[v] -= getkth(vect[v], i);
if(v) vect[par[v]].insert(dp[v]);
ret -= dp[v];
ret += getsum(vect[par[v]], i);
}
ans[i] = ret;
}
return ans;
}
*/
