#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];
vector <ll> value[N], pf[N];
int maxdeg, base = 400, 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 (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];
}
}
void DFS(int u, int p, int &curK, vector <int> &w) {
dp[u][0] = dp[u][1] = 0;
vector <ll> luu, tmp;
for (pair <int, int> 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];
}
sort(luu.begin(), luu.end());
tmp = luu;
int recur = curK, ind = value[u].size();
while (recur != 0 && !luu.empty()) {
ll csp = luu.back();
luu.pop_back();
if (ind != 0) {
int L = lower_bound(value[u].begin(), value[u].end(), csp) - value[u].begin();
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];
swap(luu, tmp);
recur = curK - 1, ind = value[u].size();
while (recur != 0 && !luu.empty()) {
ll csp = luu.back();
luu.pop_back();
if (ind != 0) {
int L = lower_bound(value[u].begin(), value[u].end(), csp) - value[u].begin();
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;//, cout << i << '\n';
for (int i = 0; i < n; ++i) {
vector <pair <int, int>> keep;
for (pair <int, int> p : g[i]) {
if (leaf[p.first]) value[i].push_back(w[p.second]);
else keep.emplace_back(p.first, p.second);//, cout << i << ' ' << p.first << '\n';
}
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]);
/*if (!value[i].empty()) {
cout << i << ":" << '\n';
for (int val : value[i]) cout << val << ' '; cout << '\n';
}*/
}
for (int i = 0; i < n; ++i) {
int r = find(i);
if (!leaf[r]) {
root = r;
break;
}
}
for (int k = base + 1; k < maxdeg; ++k) {
DFS(root, root, k, w);
ans[k] = dp[root][0] + TONG;
/*if (k == 3) {
for (int i = 0; i < n; ++i) cout << dp[i][0] << " "; cout << '\n';
for (int i = 0; i < n; ++i) cout << dp[i][1] << ' '; cout << '\n';
}*/
}
for (int i = 0; i < maxdeg; ++i) ans[i] = sum - ans[i];
return ans;
}
