#include "bits/stdc++.h"
#include "roads.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5, sq = 2000;
const ll inf = 1e18;
vector<vector<pair<int, int>>> g(N);
vector<int> par(N);
pair<ll, ll> dfs(int u, int came, int k) {
int need = (int) g[u].size() - k;
ll sum = 0;
vector<ll> vec;
vector<pair<ll, ll>> all;
for (auto [v, w]: g[u]) {
if (par[u] == v) continue;
par[v] = u;
auto it = dfs(v, w, k);
all.emplace_back(it);
if (it.first < it.second) {
vec.emplace_back(it.second - it.first);
sum += it.first;
}
else sum += it.second, need--;
}
sort(vec.begin(), vec.end());
if (need <= (int) vec.size()) for (int i = 0; i < need; i++) sum += vec[i];
else sum = inf;
vec.clear();
int need2 = (int) g[u].size() - k - 1;
ll sum2 = came;
int z = 0;
for (auto [v, w]: g[u]) {
if (par[u] == v) continue;
auto it = all[z++];
if (it.first < it.second) {
vec.emplace_back(it.second - it.first);
sum2 += it.first;
}
else sum2 += it.second, need2--;
}
sort(vec.begin(), vec.end());
for (int i = 0; i < need; i++) sum += vec[i];
// cout << u << ' ' << sum << ' ' << sum2 << ' ' << need << endl;
return {sum, sum2};
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
for (int i = 0; i < n - 1; i++) {
g[u[i]].emplace_back(v[i], w[i]);
g[v[i]].emplace_back(u[i], w[i]);
}
vector<ll> ans(n);
for (int k = 0; k < min(n, sq); k++) {
auto it = dfs(0, 0, k);
ans[k] = it.first;
}
return ans;
}
