#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
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];
vector <int> value[N];
vector <ll> pf[N];
int maxdeg, base = 350, root = -1;
bool leaf[N];
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] = dp[u][1] = 0;
vector <int> luu;
for (auto &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];
}
}
void DFS(int u, int p, int &curK, vector <int> &w) {
dp[u][0] = dp[u][1] = 0;
vector <ll> luu, tmp;
luu.reserve(g[u].size());
for (auto &P : g[u]) {
int v = P.first;
if (v == p) continue;
DFS(v, u, curK, w);
ll giatri = dp[v][1] + w[P.second] - dp[v][0];
if (giatri > 0) luu.push_back(giatri);
dp[u][1] += dp[v][0];
dp[u][0] += dp[v][0];
}
if ((int)luu.size() > curK)
nth_element(luu.begin(), luu.end() - curK, luu.end());
sort(luu.begin(), luu.end());
tmp.swap(luu);
int recur = curK, ind = value[u].size();
int ptr = ind - 1;
while (recur != 0 && !luu.empty()) {
ll csp = luu.back();
luu.pop_back();
if (ind != 0) {
while (ptr >= 0 && value[u][ptr] >= csp) ptr--;
int L = ptr + 1;
L = max(L, ind - recur);
recur -= ind - L;
dp[u][0] += pf[u][ind - 1];
if (L != 0) dp[u][0] -= pf[u][L - 1];
ind = L;
}
if (recur != 0) dp[u][0] += csp, recur--;
}
int vitri = max(ind - recur, 0);
if (ind != 0) dp[u][0] += pf[u][ind - 1];
if (vitri != 0) dp[u][0] -= pf[u][vitri - 1];
luu.swap(tmp);
recur = curK - 1, ind = value[u].size();
ptr = ind - 1;
while (recur != 0 && !luu.empty()) {
ll csp = luu.back();
luu.pop_back();
if (ind != 0) {
while (ptr >= 0 && value[u][ptr] >= csp) ptr--;
int L = ptr + 1;
L = max(L, ind - recur);
recur -= ind - L;
dp[u][1] += pf[u][ind - 1];
if (L != 0) dp[u][1] -= pf[u][L - 1];
ind = L;
}
if (recur != 0) dp[u][1] += csp, recur--;
}
vitri = max(ind - recur, 0);
if (ind != 0) dp[u][1] += pf[u][ind - 1];
if (vitri != 0) dp[u][1] -= pf[u][vitri - 1];
}
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);
}
}
for (int i = 0; i < n; ++i) if ((int)g[i].size() == 1) leaf[i] = 1;
for (int i = 0; i < n; ++i) {
vector <pair <int, int>> keep;
for (auto &p : g[i]) {
if (leaf[p.first]) value[i].push_back(w[p.second]);
else keep.emplace_back(p.first, p.second);
}
sort(value[i].begin(), value[i].end());
ll prefix = 0;
for (int val : value[i]) {
prefix += val;
pf[i].push_back(prefix);
}
swap(keep, g[i]);
}
int root = 0;
for (int i = 0; i < n; ++i)
if (g[i].size() > g[root].size()) root = i;
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;
}
