// Fight the good fight of the faith. Take hold of the
// eternal life to which you were called when you made
// your good confession in the presence of many witnesses
// 1 Timonthy 6:12
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005
int n;
vii tadj[MAXN], adj[MAXN];
vi deg[MAXN];
bool on[MAXN];
multiset<int> offw[MAXN];
set<int> useful;
bool vis[MAXN];
int k;
// first is never close parent, second is close parent
pll dp(int u, int p) {
vector<pll> vec;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
vis[v] = 1;
auto [a, b] = dp(v, u);
b += w;
vec.pb(MP(a, b));
}
sort(ALL(vec), [&] (pll l, pll r) {
return l.SE - l.FI < r.SE - r.FI;
});
auto solve = [&] (int k) {
ll res = INF, cur = 0;
int sze = offw[u].size();
for (auto [a, b] : vec) {
cur += a;
sze++;
}
int j = 0;
for (; j < vec.size() && sze > k; j++) {
auto [a, b] = vec[j];
cur -= a;
cur += b;
sze--;
}
auto ptr = offw[u].begin();
while (sze > k && ptr != offw[u].end()) {
cur += *ptr;
sze--;
}
if (sze > k) {
return LINF;
}
res = cur;
for (; j < vec.size() && ptr != offw[u].begin(); j++) {
auto [a, b] = vec[j];
cur -= a;
cur += b;
ptr = prev(ptr);
cur -= *ptr;
mnto(res, cur);
}
return res;
};
return MP(solve(k - 1), solve(k));
}
vll minimum_closure_costs(int n, vi u, vi v, vi w) {
::n = n;
REP (i, 0, n - 1) {
tadj[u[i]].pb(MP(v[i], w[i]));
tadj[v[i]].pb(MP(u[i], w[i]));
}
REP (i, 0, n) {
deg[tadj[i].size()].pb(i);
}
vll ans(n, 0);
RREP (k, n - 1, 0) {
::k = k;
debug("%d\n", k);
for (int i : deg[k + 1]) {
debug(" %d\n", i);
useful.insert(i);
on[i] = 1;
for (auto [u, w] : tadj[i]) {
if (on[u]) {
adj[u].pb(MP(i, w));
adj[i].pb(MP(u, w));
offw[u].erase(offw[u].find(w));
} else {
offw[i].insert(w);
}
}
}
for (int i : useful) {
if (vis[i]) continue;
vis[i] = 1;
auto [a, b] = dp(i, -1);
ans[k] = b;
}
for (int i : useful) {
vis[i] = 0;
}
}
return ans;
}
