#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
// const long long inf = 1e18;
const int N = 2e5 + 10;
vector<pair<int, long long>> adj[N];
long long dp[N][2];
void dfs(int node, int parent, int max_deg) {
int cnt = 0;
for(auto i: adj[node]) {
if(i.first == parent) continue;
dfs(i.first, node, max_deg);
cnt++;
}
if(cnt == 0) {
dp[node][0] = dp[node][1] = 0;
} else {
vector<pair<long long, long long>> diff;
for(auto i: adj[node]) {
if(i.first == parent) continue;
diff.push_back({dp[i.first][1] + i.second - dp[i.first][0], i.first});
}
sort(all(diff));
int curr_deg = adj[node].size();
if(max_deg >= curr_deg) {
long long to_add = 0;
for(int i = 0; i < sz(diff); i++) {
if(diff[i].first < 0) {
long long edge = diff[i].first - dp[diff[i].second][1];
edge += dp[diff[i].second][0];
//
to_add += dp[diff[i].second][1] + edge;
} else {
to_add += dp[diff[i].second][0];
}
}
dp[node][0] = dp[node][1] = to_add;
} else {
{
int qn = curr_deg - max_deg;
long long to_add = 0, cr = 0;
for(int i = 0; i < sz(diff); i++) {
if(diff[i].first < 0) {
long long edge = diff[i].first - dp[diff[i].second][1];
edge += dp[diff[i].second][0];
//
to_add += dp[diff[i].second][1] + edge;
cr++;
} else {
if(cr < qn) {
to_add += diff[i].first + dp[diff[i].second][0];
cr++;
} else{
to_add += dp[diff[i].second][0];
}
}
}
assert(cr >= qn);
dp[node][0] = to_add;
}
{
int qn = curr_deg - max_deg - 1;
long long to_add = 0, cr = 0;
for(int i = 0; i < sz(diff); i++) {
if(diff[i].first < 0) {
long long edge = diff[i].first - dp[diff[i].second][1];
edge += dp[diff[i].second][0];
//
to_add += dp[diff[i].second][1] + edge;
cr++;
} else {
if(cr < qn) {
to_add += diff[i].first + dp[diff[i].second][0];
cr++;
} else{
to_add += dp[diff[i].second][0];
}
}
}
if(cr >= qn) {
dp[node][1] = to_add;
assert(dp[node][0] >= dp[node][1]);
dp[node][0] = max(dp[node][0], to_add);
}
}
}
}
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
bool flag1 = true, flag2 = true;;
for(int i = 0; i < N - 1; i++) {
if(U[i] != 0) {
flag1 = false;
}
if(U[i] != i || V[i] != i + 1) {
flag2 = false;
}
}
if(flag1) {
sort(all(W));
vector<long long> answ(N, 0);
int it = 0;
for(int i = N - 2; i >= 0; i--) {
answ[i] = answ[i + 1] + W[it++];
}
return answ;
}
if(flag2) {
vector<long long> answ(N, 0);
for(auto i: W) {
answ[0] += i;
}
vector<vector<long long>> dp(N, vector<long long> (2, 0));
dp[0][0] = 0;
dp[0][1] = 0;
for(int i = 1; i < N; i++) {
dp[i][0] = min(dp[i - 1][1], dp[i - 1][0]) + W[i - 1];
dp[i][1] = dp[i - 1][0];
}
answ[1] = min(dp[N - 1][0], dp[N - 1][1]);
return answ;
}
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]});
}
vector<long long> answ(N, 0);
for(auto i: W) {
answ[0] += i;
}
for(int i = 1; i < N; i++) {
dfs(0, -1, i);
answ[i] = dp[0][0];
}
return answ;
}
