#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);
ll dp[N-1][2];
dp[0][0] = 0;
dp[0][1] = w[0];
dp[1][0] = w[0];
dp[1][1] = w[1];
for(int i = 2;i<N-1;i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = w[i] + dp[i-1][0];
}
ans.pb(sum - max(dp[N-2][0], dp[N-2][1]));
for(int i = 2;i<N;i++)ans.pb(0);
}
return ans;
}
