#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W){
vector<pii> g[n + 1];
ll tot = 0;
for (int i = 0; i < n - 1; i++){
int u = U[i] + 1, v = V[i] + 1, w = W[i];
g[u].pb({v, w});
g[v].pb({u, w});
tot += w;
}
vector<ll> dp[n + 1];
vector<int> ch[n + 1];
vector<int> :: iterator it;
auto get = [&](int v, int k){
it = upper_bound(ch[v].begin(), ch[v].end(), k);
int i = (int) (it - ch[v].begin()) - 1;
return dp[v][i];
};
function<void(int, int)> dfs = [&](int v, int pr){
if ((g[v].size() + !pr) == 1){
dp[v] = {0};
ch[v] = {0};
return;
}
for (auto [i, w]: g[v]){
if (i == pr) continue;
dfs(i, v);
}
vector<int> all1;
for (auto [i, w]: g[v]){
if (i == pr) continue;
for (int j: ch[i]){
all1.pb(j);
all1.pb(j + 1);
}
}
sort(all1.begin(), all1.end());
vector<int> all;
int i = 0;
while (i < all1.size()){
int j = i;
while (j < all1.size() && all1[i] == all1[j]){
j++;
}
all.pb(all1[i]);
i = j;
}
ch[v].pb(0); dp[v].pb(0);
for (int t = 1; t < all.size(); t++){
int k = all[t]; int R = (t == (all.size() - 1)) ? n : (all[t + 1] - 1);
ll sum = 0;
vector<ll> arr;
for (auto [i, w]: g[v]){
if (i == pr) continue;
sum += get(i, k);
arr.pb(get(i, k - 1) - get(i, k) + w);
}
sort(arr.begin(), arr.end(), greater<ll>());
for (int j = 0; j < min((int) arr.size(), k); j++){
if (arr[j] <= 0) break;
sum += arr[j];
}
ch[v].pb(k);
dp[v].pb(sum);
for (int j = k; j < min((int) arr.size(), R); j++){
if (arr[j] <= 0) break;
sum += arr[j];
ch[v].pb(j + 1);
dp[v].pb(sum);
}
}
};
dfs(1, 0);
vector<ll> out;
for (int i = 0; i < n; i++){
out.pb(tot - get(1, i));
}
return out;
}
