#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
typedef long long ll;
vector<ll> minimum_closure_costs(int n, vector<int> Uedges, vector<int> Vedges, vector<int> Wedges) {
const ll inf = (ll) 1e18 + 7;
assert((int) Uedges.size() == n - 1);
assert((int) Vedges.size() == n - 1);
assert((int) Wedges.size() == n - 1);
vector<vector<pair<int, int>>> g(n);
vector<int> md(n, 0);
vector<ll> dp_take(n, -inf);
vector<ll> dp_not(n, -inf);
int maxDeg;
vector<int> sub(n), value(n, 0);
for (int i = 0; i < n - 1; i++) {
g[Uedges[i]].push_back({Vedges[i], Wedges[i]});
g[Vedges[i]].push_back({Uedges[i], Wedges[i]});
}
function<void(int, int)> build = [&] (int a, int p) {
md[a] = (int) g[a].size();
sub[a] = 1;
vector<pair<int, int>> kids;
for (auto &it : g[a]) {
int b = it.first;
if (b == p) continue;
value[b] = it.second;
kids.push_back(it);
build(b, a);
sub[a] += sub[b];
md[a] = max(md[a], md[b]);
}
g[a] = kids;
};
function<void(int)> dfs = [&] (int a) {
if (g[a].empty()) {
dp_not[a] = 0;
if (1 <= maxDeg) {
dp_take[a] = value[a];
}
return;
}
assert(!g[a].empty());
int ln = min(md[a], maxDeg);
vector<ll> best(ln + 1, -inf);
best[0] = 0;
for (auto &it : g[a]) {
int b = it.first;
ll cost = it.second;
dfs(b);
vector<ll> new_best(ln + 1, -inf);
for (int bef = 0; bef <= ln; bef++) {
/// don't take it
new_best[bef] = max(new_best[bef], best[bef] + dp_not[b]);
/// take it
if (bef + 1 <= ln) {
new_best[bef + 1] = max(new_best[bef + 1], best[bef] + dp_take[b]);
}
}
best = new_best;
}
for (int d = 0; d <= ln; d++) {
dp_not[a] = max(dp_not[a], best[d]);
if (d + 1 <= maxDeg) {
dp_take[a] = max(dp_take[a], best[d] + value[a]);
}
}
};
build(0, -1);
vector<ll> print(n, 0);
for (maxDeg = 0; maxDeg < n; maxDeg++) {
for (auto &x : dp_take) x = -inf;
for (auto &x : dp_not) x = -inf;
dfs(0);
print[maxDeg] = dp_not[0];
}
{
ll totalSum = 0;
for (auto &x : Wedges) {
totalSum += x;
}
for (auto &x : print) {
x = totalSum - x;
}
}
return print;
}
