#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
vector<vector<pair<int, int>>> g(n);
bool st = 1, ln = 1;
for (int i = 0; i + 1 < n; i++) {
g[u[i]].push_back({v[i], w[i]});
g[v[i]].push_back({u[i], w[i]});
if (u[i] && v[i]) st = 0;
if (u[i] != i || v[i] != i + 1) ln = 0;
}
vector<long long> ans(n);
if (st) {
vector<long long> v;
for (auto [x, y] : g[0]) {
v.push_back(y);
}
sort(v.begin(), v.end());
for (int i = n - 2; i >= 0; i--) {
ans[i] = ans[i + 1] + v[n - i - 2];
}
return ans;
}
ans[0] = accumulate(w.begin(), w.end(), 0LL);
for (int k = 1; k < (ln ? min(2, n - 1) : n - 1); k++) {
vector<long long> dp0(n), dp1(n);
auto dfs = [&](const auto &dfs, int u) -> void {
vector<long long> del;
for (auto [v, w] : g[u]) {
if (k == 1) g[v].erase(find(g[v].begin(), g[v].end(), make_pair(u, w)));
dfs(dfs, v);
del.push_back(dp1[v] - dp0[v] + w);
dp0[u] += dp0[v];
dp1[u] += dp0[v];
}
sort(del.begin(), del.end());
int cnt = 0;
for (auto x : del) {
if (x <= 0) {
dp0[u] += x;
dp1[u] += x;
cnt++;
} else {
break;
}
}
for (int i = cnt; i < (int) g[u].size() - k + 1; i++) {
dp0[u] += del[i];
}
for (int i = cnt; i < (int) g[u].size() - k; i++) {
dp1[u] += del[i];
}
};
dfs(dfs, 0);
ans[k] = dp1[0];
}
return ans;
}
