#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 205;
int n;
ll total = 0;
ll dp[MAXN][MAXN];
#define w(i) i.first
#define u(i) i.second
vector<pair<int, int>> con[MAXN];
ll solve(int curr, int par, int k){
if (k < 0)
return -LONG_LONG_MAX;
if (dp[curr][k] != -1)
return dp[curr][k];
vector<pair<ll, int>> best, out, dif;
for (auto i : con[curr]){
if (u(i) == par)
continue;
best.push_back({solve(u(i), curr, k - 1) + w(i), u(i)});
}
for (auto i : con[curr]){
if (u(i) == par)
continue;
out.push_back({solve(u(i), curr, k), u(i)});
}
for (int i = 0; i < best.size(); i++)
dif.push_back({best[i].first - out[i].first, i});
ll res = 0;
vector<bool> used (best.size(), false);
sort(dif.begin(), dif.end(), greater<pair<ll, int>>());
for (auto i : out)
res += i.first;
for (int i = 0; i < k and i < best.size(); i++)
if (dif[i].first > 0)
res += dif[i].first;
dp[curr][k] = res;
return res;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
for (int i = 0; i < n - 1; i++)
con[U[i]].push_back({W[i], V[i]}), con[V[i]].push_back({W[i], U[i]}), total += W[i];
vector<ll> res;
for (int k = 0; k < n; k++){
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i][j] = -1;
res.push_back(total - solve(0, -1, k));
}
return res;
}
