#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e5+5; ll N;
const ll K = 300;
ll ans[Nm];
vector<pii> adj[Nm];
vector<ll> fadj[Nm];
ll deg[Nm];
pii radj[Nm]; //{number, cost}
vector<ll> itpl; //inverse topological sort
ll slvH(ll k) {
ll dp0[N]; //no path up
ll dp1[N]; //path up
for (ll i=(N-1);i>=0;i--) {
ll x = itpl[i];
vector<ll> vaug; //augment vector
ll val0 = 0; //minimum value
for (ll y: fadj[x]) {
val0 += dp0[y];
vaug.push_back(dp1[y]-dp0[y]);
}
sort(vaug.begin(),vaug.end());
ll NDEL = max(0LL,deg[x]-k);
dp0[x]=val0;
for (ll j=0;j<NDEL;j++) {
dp0[x]+=vaug[j];
}
NDEL = max(0LL,deg[x]-k-1);
dp1[x]=val0+radj[x].second;
for (ll j=0;j<NDEL;j++) {
dp1[x]+=vaug[j];
}
if (x!=0) {
dp0[x]=min(dp1[x],dp0[x]);
}
}
return dp0[0];
}
vector<ll> minimum_closure_costs(int N1, vector<int> U, vector<int> V, vector<int> W) {
N=N1;
for (ll i=0;i<N;i++) {
adj[i].clear();
fadj[i].clear();
}
itpl.clear();
ll sroad = 0;
for (ll i=0;i<(N-1);i++) {
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
sroad += W[i];
}
for (ll i=0;i<N;i++) {
deg[i]=adj[i].size();
}
queue<ll> q0;
q0.push(0); //root is 0
radj[0]={-1,-1};
while (!q0.empty()) {
ll x = q0.front(); q0.pop();
itpl.push_back(x);
for (pii p0: adj[x]) {
if (p0.first!=radj[x].first) {
fadj[x].push_back(p0.first);
radj[p0.first]={x,p0.second};
q0.push(p0.first);
}
}
}
for (ll k=1;k<N;k++) {
ans[k]=slvH(k);
}
ans[0]=sroad;
vector<ll> ansF(N,0);
for (ll i=0;i<N;i++) {
ansF[i]=ans[i];
}
return ansF;
}
