#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
int k;
vector<vector<pair<int,int>>> edges;
pair<long long,long long> dfs(int cur,int par){
vector<pair<long long,long long>> child;// not delete parent, delete parent
for(auto [nxt,w]:edges[cur]){
if(nxt == par)continue;
auto [np,cp] = dfs(nxt,cur);
child.push_back({np,cp+w});
}
long long base = 0;
vector<int> diff;
for(auto [np,cp]:child){
base += np;
diff.push_back(cp-np);
}
sort(diff.begin(),diff.end());
int out = 1+child.size();
int del = out-k;// k must greater than 1
pair<long long,long long> result;// not delete parent, delete parent
long long ndelp = base,delp = base;
// ndel parent, (all del on child)
for(int i = 0;i < del;i++){
ndelp += diff[i];
}
// not chose p,
for(int i = 0;i < del-1;i++){
delp += diff[i];
}
return {ndelp,delp};
// greedy;
}
vector<long long> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) {
// N^2 solution
vector<long long> ans(N,0);
edges.resize(N);
for(int i = 0;i < N-1;i++){
edges[U[i]].push_back({V[i],W[i]});
edges[V[i]].push_back({U[i],W[i]});
}
for(auto i:W) ans[0] += i;
for(int i = 1;i <= N-1;i++){
k = i;
pair<long long,long long> res = dfs(0,-1);
ans[i] = min(res.first,res.second);
}
return ans;
}
// // grader
// #include "roads.h"
// #include <cassert>
// #include <cstdio>
// #include <vector>
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> U(N - 1), V(N - 1), W(N - 1);
// for (int i = 0; i < N - 1; ++i) {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
// std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
// for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%lld",closure_costs[i]);
// }
// printf("\n");
// return 0;
// }
