#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
set<pair<int, int>> adj[maxN];
vector<pair<int, int>> pre_adj[maxN];
vector<int> bucket[maxN];
int deg[maxN];
bool is_bad[maxN];
bool flag[maxN];
long long dp[maxN][2];
int K;
void dfs(int u, int par) {
flag[u] = true;
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 cnt = cost.size();
for (int i = 0; i < 2; i++) {
if (cnt + i <= K) {
dp[u][i] = min(dp[u][i], sum);
}
}
for (auto w: cost) {
sum += w;
cnt--;
for (int i = 0; i < 2; i++) {
if (cnt + 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++) {
pre_adj[U[i]].push_back({V[i], W[i]});
pre_adj[V[i]].push_back({U[i], W[i]});
deg[U[i]]++;
deg[V[i]]++;
}
for (int i = 0; i < N; i++) {
bucket[deg[i]].push_back(i);
}
vector<long long> res(N);
vector<int> bad;
for (K = N - 1; K >= 0; K--) {
//cout << "calc" << " " << K << '\n';
for (auto u: bad) {
flag[u] = false;
}
for (auto u: bad) {
if (!flag[u]) {
dfs(u, -1);
res[K] += dp[u][0];
}
}
for (auto u: bucket[K]) {
//cout << "add" << " " << u << '\n';
for (auto e: pre_adj[u]) {
int v = e.first;
int w = e.second;
adj[u].insert({v, w});
adj[v].insert({u, w});
}
bad.push_back(u);
is_bad[u] = true;
}
}
return res;
}
