#include "roads.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
#define ll long long int
#define vi vector<ll>
using namespace std;
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vi r(N, 0);
f0r(i,N-1){
r[U[i]]++;
r[V[i]]++;
}
vector<long long int> ans;
vi w;
f0r(i,N-1)w.pb(W[i]);
if(r[0] == N-1){
sort(w.begin(), w.end());
ll sum = 0;
ans.pb(0);
f0r(i,N-1){
sum += w[i];
ans.pb(sum);
}
reverse(ans.begin(), ans.end());
}
else{
ll sum = 0;
f0r(i, N-1)sum += w[i];
ans.pb(sum);
if(N % 2 == 0){
ll od = 0;
ll ev = 0;
f0r(i, N-1){
if(i % 2 == 0)ev += w[i];
else od += w[i];
}
ans.pb(min(ev, od));
}
else{
ll cur = 0;
f0r(i, N-1){
if(i % 2 == 0){
cur+=w[i];
}
}
ll mx = cur;
for(int i = N-2; i>=1;i-=2){
cur += w[i];
cur -= w[i-1];
mx = max(mx, cur);
}
ans.pb(sum - mx);
}
for(int i = 2;i<N;i++)ans.pb(0);
}
return ans;
}
