#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
vector<pair<int, int>> adj[maxN];
long long dp[maxN][2];
int K;
void dfs(int u, int par) {
dp[u][0] = inf;
dp[u][1] = inf;
long long sum = 0;
vector<long long> cost;
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (v == par) {
continue;
}
dfs(v, u);
sum += dp[v][1];
cost.push_back(dp[v][0] + w - dp[v][1]);
}
sort(cost.begin(), cost.end());
int deg = cost.size();
for (int i = 0; i < 2; i++) {
if (deg + i <= K) {
dp[u][i] = min(dp[u][i], sum);
}
}
for (auto w: cost) {
sum += w;
deg--;
for (int i = 0; i < 2; i++) {
if (deg + i <= K) {
dp[u][i] = min(dp[u][i], sum);
}
}
}
}
vector<long long> 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]});
}
vector<long long> res(N);
for (K = 0; K <= N - 1; K++) {
dfs(0, -1);
res[K] = dp[0][0];
}
return res;
}
