#include "roads.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
using ll = long long;
int done[100005], vis[100005];
int ct[100005];
vector<int> deg[100005], W;
vector<pii> adj[100005];
ll dp[100005][2]; //0 cut par, 1 cut child
int addidx[100005];
void dfs(int u, int p, int mx) {
vis[u] = 1;
dp[u][0] = dp[u][1] = 0;
bool one = 0;
for(auto [v, i]:adj[u]) {
int w = W[i];
if(v==p || ct[v]<=mx || done[i]) continue;
dfs(v, u, mx);
dp[u][0] += min(dp[v][0]+w, dp[v][1]);
dp[u][1] += min(dp[v][0]+w, dp[v][1]);
if(dp[v][0]+w<dp[v][1]) one = 1;
}
addidx[u] = -1;
if(!one) {
ll add = 1e18;
for(auto [v, i]:adj[u]) {
int w = W[i];
if(v==p || ct[v]<=mx || done[i]) continue;
ll val = min(dp[v][0], dp[v][1])+w-dp[v][1];
if(val<add) {
add = val;
addidx[u] = i;
}
}
if(add==1e18) {
for(auto [v, i]:adj[u]) {
int w = W[i];
if(v==p || done[i]) continue;
ll val = min(dp[v][0], dp[v][1])+w-dp[v][1];
if(w<add) {
add = val;
addidx[u] = i;
}
}
}
dp[u][1] += add;
}
}
void dfsback(int u, int p, int mx, int j) {
for(auto [v, i]:adj[u]) {
int w = W[i];
if(j==1 && addidx[u]==i) {
done[i] = 2;
dfsback(v, u, mx, (dp[v][0]<=dp[v][1] ? 0:1));
continue;
}
if(v==p || ct[v]<=mx || done[i]) continue;
if(dp[v][0]+w<=dp[v][1]) {
done[i] = 2;
dfsback(v, u, mx, 0);
} else {
dfsback(v, u, mx, 1);
}
}
}
vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> ww) {
W = ww;
for(int i=0;i<n-1;i++) {
ct[U[i]]++;
ct[V[i]]++;
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
for(int i=0;i<n;i++) {
deg[ct[i]].push_back(i);
}
vector<long long> ans(n, 0);
for(int i=n-1;i>=0;i--) {
for(int j=0;j<n;j++) vis[j] = 0;
if(i<n-1) ans[i] = ans[i+1];
for(int u=0;u<n;u++) {
if(ct[u]<=i || vis[u]) continue;
dfs(u, -1, i);
ans[i] += dp[u][1];
dfsback(u, -1, i, 1);
}
for(int j=0;j<n-1;j++) {
if(done[j]==2) {
done[j] = 1;
ct[U[j]]--;
ct[V[j]]--;
}
}
}
return ans;
}
