#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 3, mod = 998244353, inf = 2e9;
ll dp[N][2];
void dfs(int u, int p, int &curK, vector<vector<pair<int, int>>> &g, vector <int> &w) {
dp[u][0] = 0;
dp[u][1] = 0;
vector <int> luu;
for (pair <int, int> P : g[u]) {
int v = P.first;
if (v == p) continue;
dfs(v, u, curK, g, w);
luu.push_back(dp[v][1] + w[P.second] - dp[v][0]);
dp[u][1] += dp[v][0];
dp[u][0] += dp[v][0];
}
sort(luu.begin(), luu.end(), greater <int> ());
for (int i = 0; i < min((int)luu.size(), curK); ++i) {
if (luu[i] < 0) break;
dp[u][0] += luu[i];
if (i != curK - 1) dp[u][1] += luu[i];
}
}
vector <ll> minimum_closure_costs(int n, vector <int> u, vector <int> v, vector <int> w) {
vector <ll> ans(n, 0);
vector <vector<pair<int, int>>> g(n);
ll sum = 0;
for (int i = 0; i < n - 1; ++i) {
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
sum += w[i];
}
for (int k = 0; k < n; ++k) {
dfs(0, 0, k, g, w);
for (int i = 0; i < n; ++i) ans[k] = max(ans[k], dp[i][0]);
}
for (int i = 0; i < n; ++i) ans[i] = sum - ans[i];
return ans;
}
