#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 3, mod = 998244353, inf = 2e9;
ll dp[N][2], lab[N], sum, TONG;
vector <pair<int, int>> g[N];
int maxdeg, base = 350, root = -1;
int find(int u) {
return (lab[u] < 0 ? u : lab[u] = find(lab[u]));
}
void unite(int r, int s) {
if (lab[r] > lab[s]) swap(r, s);
lab[r] += lab[s];
lab[s] = r;
}
void dfs(int u, int p, int &curK, 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, 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);
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];
maxdeg = max({maxdeg, (int)g[u[i]].size(), (int)g[v[i]].size()});
if ((int)g[u[i]].size() > base) root = u[i];
if ((int)g[v[i]].size() > base) root = v[i];
}
for (int k = 0; k < min(maxdeg, base + 1); ++k) {
dfs(0, 0, k, w);
ans[k] = dp[0][0];
}
for (int i = 0; i < n; ++i) lab[i] = -1;
for (int i = 0; i < n - 1; ++i) {
if ((int)g[u[i]].size() > base || (int)g[v[i]].size() > base) continue;
TONG += w[i];
int r = find(u[i]), s = find(v[i]);
if (r != s) unite(r, s);
}
for (int i = 0; i < n; ++i) g[i].clear();
for (int i = 0; i < n - 1; ++i) {
int x = find(u[i]);
int y = find(v[i]);
if (x != y) {
g[x].emplace_back(y, i);
g[y].emplace_back(x, i);
}
}
int root = find(0);
for (int k = base + 1; k < maxdeg; ++k) {
dfs(root, root, k, w);
ans[k] = dp[root][0] + TONG;
}
for (int i = 0; i < maxdeg; ++i) ans[i] = sum - ans[i];
return ans;
}
