#include "roads.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
bool visited[100000], B[100000];
ll f, z, dp[100000][2];
vector <ll> deg[100000];
vector <ll> X, F;
vector <array<ll, 2>> adj[100000];
void dfs(ll u, ll p) {
visited[u] = 1;
priority_queue <ll, vector <ll>, greater<ll> > pq;
ll res = 0;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
if (B[v]) dfs(v, u);
else dp[v][0] = dp[v][1] = 0;
res += dp[v][1] + w;
pq.push(dp[v][0] - dp[v][1] - w);
}
for (int i=0; i<z-1; ++i) {
if (pq.empty()) break;
auto x = pq.top();
pq.pop();
if (x >= 0) break;
res += x;
}
dp[u][0] = res;
if (z && !pq.empty()) {
ll x = pq.top();
if (x < 0) res += x;
}
dp[u][1] = res;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::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[adj[i].size()-1].push_back(i);
}
for (int i=N-1; i>=0; --i) {
z = i, f = 0;
for (auto u : deg[i]) {
B[u] = 1;
X.push_back(u);
}
for (auto u : X) visited[u] = 0;
for (auto u : X) {
if (!visited[u]) {
dfs(u, -1);
f += dp[u][1];
}
}
F.push_back(f);
}
reverse(F.begin(), F.end());
return F;
}
