#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> d,u,v,w;
ll get(int i,int k){
ll ans = (d[u[i]] > k) + (d[v[i]] > k);
return ans;
}
ll inf = (int)1e9;
ll cost(int i,int k){
int _ = get(i,k);
if(_ ==0) return -1;
if(_ == 1) return inf + w[i];
return w[i];
}
const int maxn = (int)1e5 +12;
vector<pair<int,int>> g[maxn];
int vis[maxn];
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W) {
u = U;
v = V;
w = W;
vector<int> deg(N,0);
for(int i = 0;i < N - 1;i++){
deg[U[i]]++;
deg[V[i]]++;
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
vector<ll> ans;
int timer = 0;
for(int i = 0;i < N;i++){
timer++;
d = deg;
set<pair<ll,int>> st;
ll res = 0;
for(int j = 0;j < N - 1;j++){
ll A = cost(j,i);
if(A == -1) continue;
st.insert({A,j});
}
while(!st.empty()){
auto [c,j] = (*st.begin());
vis[j] = timer;
assert(c != -1);
res += w[j];
st.erase({c,j});
int x = u[j],y = v[j];
d[x]--;d[y]--;
for(auto [to,id]:g[x]){
if(vis[id] == timer) continue;
if(to == y) continue;
d[x]++;
st.erase({cost(id,i),id});
d[x]--;
ll A = cost(id,i);
if(A != -1){
st.insert({A,id});
}
}
for(auto [to,id]:g[y]){
if(vis[id] == timer) continue;
if(to == x) continue;
d[y]++;
st.erase({cost(id,i),id});
d[y]--;
ll A = cost(id,i);
if(A != -1){
st.insert({A,id});
}
}
}
if((int)ans.size()){
assert(res <= ans.back());
}
ans.push_back(res);
}
return ans;
}
