#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=1e5+5;
const ll B=200;
vector<pll> adj[mxN];
vector<pll> adj2[mxN];
vll v[mxN];
vll pre[mxN];
vll big;
bool pus[mxN];
bool visited[mxN];
ll n;
ll dp[mxN][2];
ll k;
void dfs(ll cur, ll par){
ll dumb=0;
vll tep;
for(auto &[chd, w]:adj[cur]){
if(chd==par) continue;
dfs(chd, cur);
dumb+=dp[chd][1];
if(dp[chd][0]-dp[chd][1]+w>0) tep.pb(dp[chd][0]-dp[chd][1]+w);
}
sort(tep.begin(), tep.end(), greater<ll>());
dp[cur][0]=dumb;
for(ll i=0;i<k-1 && i<(ll) tep.size();i++){
dp[cur][0]+=tep[i];
}
dp[cur][1]=dumb;
for(ll i=0;i<k && i<(ll) tep.size();i++){
dp[cur][1]+=tep[i];
}
}
void dfs2(ll cur, ll par){
visited[cur]=1;
ll dumb=0;
vll tep;
for(auto &[chd, w]:adj2[cur]){
if(chd==par) continue;
dfs2(chd, cur);
dumb+=dp[chd][1];
if(dp[chd][0]-dp[chd][1]+w>0) tep.pb(dp[chd][0]-dp[chd][1]+w);
}
sort(tep.begin(), tep.end(), greater<ll>());
dp[cur][0]=dumb;
ll len=k-1;
for(ll i=0;i<k-1 && i<(ll) tep.size();i++){
if(len-1>=(ll) v[cur].size() || tep[i]>v[cur][len-1]){
dp[cur][0]+=tep[i];
len--;
}
else{
break;
}
}
dp[cur][0]+=pre[cur][min(len, (ll) pre[cur].size()-1)];
dp[cur][1]=dumb;
len=k;
for(ll i=0;i<k && i<(ll) tep.size();i++){
if(len-1>=(ll) v[cur].size() || tep[i]>v[cur][len-1]){
dp[cur][1]+=tep[i];
len--;
}
else{
break;
}
}
dp[cur][1]+=pre[cur][min(len, (ll) pre[cur].size()-1)];
}
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
memset(pus, 0, sizeof(pus));
n=N;
ll sum=0;
for(ll i=0;i<n-1;i++){
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
sum+=W[i];
}
vll ans(n);
for(ll i=0;i<n && i<=B;i++){
k=i;
dfs(0, -1);
ans[i]=sum-dp[0][1];
}
for(ll i=0;i<n;i++){
if((ll) adj[i].size()<=B){
pus[i]=0;
}
else{
pus[i]=1;
big.pb(i);
}
}
ll sum2=0;
for(ll i=0;i<n-1;i++){
if(!pus[U[i]] && !pus[V[i]]){
sum2+=W[i];
}
else if(!pus[U[i]]){
v[V[i]].pb(W[i]);
}
else if(!pus[V[i]]){
v[U[i]].pb(W[i]);
}
else{
adj2[U[i]].pb({V[i], W[i]});
adj2[V[i]].pb({U[i], W[i]});
}
}
for(ll i=0;i<n;i++){
sort(v[i].begin(), v[i].end(), greater<ll>());
ll p=0;
pre[i].pb(p);
for(auto &it:v[i]){
p+=it;
pre[i].pb(p);
}
}
for(ll i=B+1;i<n;i++){
k=i;
ans[i]=sum2;
for(auto &it:big){
visited[it]=0;
}
for(auto &it:big){
if(!visited[it]){
dfs2(it, -1);
ans[i]+=dp[it][1];
}
}
ans[i]=sum-ans[i];
}
return ans;
}
