#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
void dfs(int st, vector<array<int,2>>g[], int p, long long dp[][2][N]){
int n = N;
int parw = 0;
for(array<int,2>e:g[st]){
if(e[0]==p){
parw=e[1];
continue;
}
dfs(e[0],g,st,dp);
}
for(int i = 0;i<n;i++){
//dp[st][0][i] to be found
vector<long long>deltas;
for(array<int,2>e:g[st]){
if(e[0]==p){
continue;
}
dp[st][0][i]+=dp[e[0]][0][i];
deltas.push_back(dp[e[0]][1][i]-dp[e[0]][0][i]);
}
sort(deltas.begin(),deltas.end());
reverse(deltas.begin(),deltas.end());
dp[st][1][i]=dp[st][0][i];
for(int ind = 0;ind<min(i,(int)deltas.size());ind++){
dp[st][0][i]+=max(0LL,deltas[ind]);
}
for(int ind = 0;ind<min(i-1,(int)deltas.size());ind++){
dp[st][1][i]+=max(0LL,deltas[ind]);
}
if(i){
dp[st][1][i]+=parw;
}
}
}
vector<long long> minimum_closure_costs(int n, vector<int> u,vector<int> v,vector<int> w) {
//star case:
vector<long long>fin;
sort(w.begin(),w.end());
fin.push_back(w[0]);
for(int i = 1;i<n-1;i++){
fin.push_back(fin.back()+w[i]);
}
reverse(fin.begin(),fin.end());
fin.push_back(0);
return fin;
vector<array<int,2>>g[n];
long long tot = 0;
for(int i = 0;i<n-1;i++){
g[u[i]].push_back({v[i],w[i]});
tot+=w[i];
g[v[i]].push_back({u[i],w[i]});
}
long long dp[n][2][N];
for(int i = 0;i<n;i++){
fill(dp[i][0],dp[i][0]+N,0);
fill(dp[i][1],dp[i][1]+N,0);
}
dfs(0,g,-1,dp);
vector<long long>ans;
for(int i = 0;i<n;i++){
ans.push_back(tot-dp[0][0][i]);
}
return ans;
}
