#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);
vector<multiset<lint>> ds(N);
vector<lint> sum(N);
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);
};
for(int i = 1; i < N; i++){
dp[i] = -pae[i];
ds[par[i]].insert(dp[i]);
sum[par[i]] += dp[i];
}
for(int k = N - 2; k > 0; k--){
ans[k] = ans[k + 1];
for(auto &j : dfn){
if(sz(gph[j]) > k){
ans[k] -= getkth(ds[j], k+1);
sum[j] -= getkth(ds[j], k+1);
}
}
for(auto &j : dfn){
if(sz(gph[j]) < k-1) continue;
if(j != 0){
ans[k] -= sum[par[j]];
ds[par[j]].erase(ds[par[j]].find(dp[j]));
}
dp[j] = min(-getkth(ds[j], k) - pae[j], 0ll);
if(j != 0){
ds[par[j]].insert(dp[j]);
sum[par[j]] = getsum(ds[par[j]], k);
ans[k] += sum[par[j]];
}
}
}
return ans;
}
