#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#endif
struct kset {
int n = 1e9;
multiset<long long, greater<long long>> s;
long long sum = 0;
vector<pair<int, long long>> ops;
void clip(int k) {
n = k;
while ((int) s.size() > n) {
sum -= *s.begin();
s.erase(s.begin());
}
}
void insert(long long x) {
sum += x;
s.insert(x);
ops.emplace_back(1, x);
if ((int) s.size() > n) {
sum -= *s.begin();
ops.emplace_back(0, *s.begin());
s.erase(s.begin());
}
}
void rollback() {
while (!ops.empty()) {
auto [t, x] = ops.back();
ops.pop_back();
if (t == 1) {
sum -= x;
assert(s.find(x) != s.end());
s.erase(s.find(x));
} else {
sum += x;
s.insert(x);
}
}
}
};
std::vector<long long> minimum_closure_costs(int n, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
vector<int> deg(n);
vector<long long> ans(n);
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; i++) {
ans[0] += W[i];
deg[U[i]]++; deg[V[i]]++;
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end(), [&](auto u, auto v) {
return deg[u.first] > deg[v.first];
});
}
vector<int> par(n, -1);
vector<int> up(n, -1);
function<void(int, int)> calc = [&](int u, int p) {
for (auto [v, w] : g[u]) {
if (v != p) {
par[v] = u;
up[v] = w;
calc(v, u);
}
}
};
calc(0, -1);
vector<kset> weights(n);
vector<vector<long long>> dp(n, vector<long long>(2));
function<void(int, int, int)> dfs = [&](int u, int p, int k) {
weights[u].clip(deg[u] - k);
weights[u].ops.clear();
long long dp_sum = 0;
for (auto [v, w] : g[u]) {
if (v != p) {
if (deg[v] <= k) {
break;
}
dfs(v, u, k);
long long mn = min(dp[v][0], dp[v][1]);
dp_sum += mn;
weights[u].insert(dp[v][1] - mn);
}
}
assert(!weights[u].s.empty());
dp[u][0] = dp_sum + weights[u].sum;
dp[u][1] = dp_sum + weights[u].sum - *weights[u].s.begin() + up[u];
weights[u].rollback();
};
vector<int> big(n);
iota(big.begin(), big.end(), 0);
sort(big.begin(), big.end(), [&](int i, int j) {
return deg[i] > deg[j];
});
for (int k = 1; k < n; k++) {
while (!big.empty()) {
int u = big.back();
if (deg[u] > k) {
break;
}
big.pop_back();
if (u != 0) {
weights[par[u]].insert(up[u]);
}
}
for (int u : big) {
if (u == 0 || deg[par[u]] <= k) {
dfs(u, par[u], k);
if (u == 0) {
ans[k] += dp[u][0];
} else {
ans[k] += min(dp[u][0], dp[u][1]);
}
}
}
}
return ans;
}
