#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "roads.h"
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
const int N = 100'005;
vector<array<int, 2>> adj[N];
ll dp[N][2];
int deg[N];
vector<int> order;
array<ll, 2> par[N];
void build(int i, int p) {
vector<array<int, 2>> newadj;
for (auto [nxt, w] : adj[i]) {
if (nxt == p) continue;
build(nxt, i);
par[nxt] = {i, w};
newadj.push_back({nxt, w});
}
adj[i] = newadj;
order.push_back(i);
}
priority_queue<ll> taken[N];
priority_queue<ll, vector<ll>, greater<ll>> pending[N];
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < n - 1; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
for (int i = 0; i < n; i++) {
deg[i] = adj[i].size();
}
build(0, -1);
par[0] = {0, (int)1e18};
vector<ll> ret(n);
for (int m = 0; m < n; m++) {
for (auto i : order) {
dp[i][1] = 0;
dp[i][0] = par[i][1];
vector<ll> vals;
for (auto [nxt, w] : adj[i]) {
dp[i][1] += dp[nxt][1];
dp[i][0] += dp[nxt][1];
vals.push_back(dp[nxt][0] - dp[nxt][1]);
}
sort(vals.begin(), vals.end());
int cnt = max(0, deg[i] - m - 1);
for (int j = 0; j < cnt; j++) {
dp[i][0] += vals[j];
}
cnt = max(0, deg[i] - m);
if (cnt == deg[i]) {
dp[i][1] = 1e18;
} else {
for (int j = 0; j < cnt; j++) {
dp[i][1] += vals[j];
}
}
dp[i][1] = min(dp[i][1], dp[i][0]);
}
ret[m] = dp[0][1];
}
return ret;
}
