#include "roads.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 100008
const long long inf = 1e18;
using namespace std;
typedef pair<long long, long long> pii;
long long n, sub1 = true, sub2 = true;
long long dp[2008][2008][2];
long long f[5][nmax][2];
vector<pii> l[nmax];
long long sdq(int id, int x, int pre, int kt){
if (f[id][x][kt] != -1)
return f[id][x][kt];
if (!id && kt)
return f[id][x][kt] = inf;
long long res = 0;
vector<long long>vt;
for (pii it : l[x])
if (it.fi != pre){
res += sdq(id, it.fi, x, 1);
vt.push_back(sdq(id, it.fi, x, 0) + it.se - sdq(id, it.fi, x, 1));
}
sort(vt.begin(), vt.end(), greater<long long>());
while (!vt.empty() && ((int)vt.size() + kt > id || vt.back() < 0)){
res += vt.back();
vt.pop_back();
}
return f[id][x][kt] = res;
}
long long dq(int id, int x, int pre, int kt){
if (dp[id][x][kt] != -1)
return dp[id][x][kt];
if (!id && kt)
return dp[id][x][kt] = inf;
long long res = 0;
vector<long long>vt;
for (pii it : l[x])
if (it.fi != pre){
res += dq(id, it.fi, x, 1);
vt.push_back(dq(id, it.fi, x, 0) + it.se - dq(id, it.fi, x, 1));
}
sort(vt.begin(), vt.end(), greater<long long>());
while (!vt.empty() && ((int)vt.size() + kt > id || vt.back() < 0)){
res += vt.back();
vt.pop_back();
}
return dp[id][x][kt] = 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 (long long i = 0; i < n - 1; i++){
if (U[i] != 0)
sub1 = false;
if (U[i] != i || V[i] != i + 1)
sub2 = false;
l[U[i]].push_back({V[i], W[i]});
l[V[i]].push_back({U[i], W[i]});
}
vector<long long>res;
if (sub1){
sort(W.begin(), W.end(), greater<int>());
long long j = 0;
for (int tmp : W)
j += tmp;
res.push_back(j);
for (long long i = 0; i < n - 1; i++){
j -= W[i];
res.push_back(j);
}
return res;
}
if (sub2){
memset(f, -1, sizeof(f));
for (long long k = 0; k < n; k++)
if (k < 2)
res.push_back(sdq(k, 0, 0, 0));
else
res.push_back(0);
return res;
}
assert(n <= 2000);
memset(dp, -1, sizeof(dp));
for (long long k = 0; k < n; k++)
res.push_back(dq(k, 0, 0, 0));
return res;
}
