#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 3, mod = 998244353, inf = 2e9;
vector <ll> minimum_closure_costs(int n, vector <int> u, vector <int> v, vector <int> w) {
vector <ll> ans(n);
vector <vector<int>> g(n);
vector <int> sz(n);
ans[n - 1] = 0;
for (int k = n - 2; k >= 0; --k) {
for (int i = 0; i < n; ++i) sz[i] = 0, g[i].clear();
for (int i = 0; i < n - 1; ++i) g[u[i]].push_back(i), g[v[i]].push_back(i), sz[u[i]]++, sz[v[i]]++;
vector <int> heavy, big;
for (int i = 0; i < n - 1; ++i) if (sz[u[i]] > k && sz[v[i]] > k) heavy.push_back(i);
for (int i = 0; i < n; ++i) if (sz[i] > k) big.push_back(i);
sort(heavy.begin(), heavy.end(), [&](int i, int j) {
return w[i] < w[j];
});
for (int id : heavy) {
int x = u[id], y = v[id];
if (sz[x] <= k || sz[y] <= k) continue;
ans[k] += w[id];
int idd = 0;
for (int i = 0; i < sz[x]; ++i) if (g[x][i] == id) idd = i;
swap(g[x][idd], g[x].back());
g[x].pop_back();
sz[x]--;
idd = 0;
for (int i = 0; i < sz[y]; ++i) if (g[y][i] == id) idd = i;
swap(g[y][idd], g[y].back());
g[y].pop_back();
sz[y]--;
}
for (int ver : big) {
sort(g[ver].begin(), g[ver].end(), [&](int i, int j) {
return w[i] > w[j];
});
while (sz[ver] > k) {
int idd = g[ver].back();
g[ver].pop_back();
sz[ver]--;
ans[k] += w[idd];
int x = u[idd];
if (x == ver) x = v[idd];
int rid = 0;
for (int i = 0; i < sz[x]; ++i) if (g[x][i] == idd) rid = i;
swap(g[x][rid], g[x].back());
g[x].pop_back();
sz[x]--;
}
}
}
return ans;
}
