#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
vector<int> g[N];
ll dp[N][2];
map<pair<int, int>, int> id;
void dfs(int v, int p, int k, vector<int> &w) {
for(auto u : g[v]) {
if(u == p) continue;
dfs(u, v, k, w);
}
priority_queue<pair<ll, ll>> vals;
for(auto u : g[v]) {
if(u == p) continue;
vals.push({dp[u][0] - dp[u][1], dp[u][1]});
}
int cnt = 0, cnt2 = 1;
while(!vals.empty()) {
auto [x, y] = vals.top(); vals.pop();
if(x > 0 && cnt + 1 <= k) {
dp[v][0] += y;
cnt++;
} else {
dp[v][0] += x + y;
}
if(x > 0 && cnt2 + 1 <= k) {
dp[v][1] += y;
cnt2++;
} else {
dp[v][1] += x + y;
}
}
if(v > 0) dp[v][0] += w[id[{v, p}]];
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
for(int i = 0; i < n - 1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
id[{u[i], v[i]}] = i;
id[{v[i], u[i]}] = i;
}
vector<ll> res;
for(int k = 0; k <= n - 1; k++) {
for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = 0;
dfs(0, -1, k, w);
res.push_back(dp[0][0]);
}
return res;
}
// int main() {
// auto r = minimum_closure_costs(4, {0, 1, 2}, {1, 2, 3}, {1, 1000000000, 2});
// for(auto x : r) cout << x << " "; cout << '\n';
// }
