#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using pil = pair<int, ll>;
const ll INF = 1'000'000'000'000'000'000;
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<pil>> edgelist(N);
for (int i=0; i<(N-1); i++)
{
int u = U[i];
int v = V[i];
ll w = W[i];
edgelist[u].push_back({v, w});
edgelist[v].push_back({u, w});
}
//root the tree
vector<int> bfs_order;
vector<bool> visited(N, 0);
vector<vector<pil>> children(N);
visited[0] = 1;
bfs_order.push_back(0);
int total = 1;
int curr = 0;
while (curr < total)
{
int curr_node = bfs_order[curr];
curr++;
for (pil edge: edgelist[curr_node])
{
int neigh = edge.first; ll weight = edge.second;
if (visited[neigh] == 0)
{
visited[neigh] = 1;
bfs_order.push_back(neigh);
total++;
children[curr_node].push_back(edge);
}
}
}
vector<ll> answer_compilation(N, 0);
for (int allowed = 1; allowed < N; allowed++)
{
vector<ll> dp1(N, INF);// can keep allowed
vector<ll> dp2(N, INF);// can keep allowed - 1
for (int index = N-1; index>=0; index--)
{
int curr_node = bfs_order[index];
ll total = 0;
vector<ll> choice;
for (pil child: children[curr_node])
{
int childnode = child.first;
ll childweight = child.second;
ll required = dp1[childnode]+childweight;
ll alternative = dp2[childnode];
if (alternative < required)
choice.push_back(alternative-required);
total+=required;
}
sort(choice.begin(), choice.end());
int choicesize = choice.size();
int aa; ll total_benefit;
aa = min(allowed-1, choicesize);
total_benefit = 0;
for (int i=0; i<aa; i++)
total_benefit = total_benefit+choice[i];
dp2[curr_node] = total+total_benefit;
aa = min(allowed, choicesize);
total_benefit = 0;
for (int i=0; i<aa; i++)
total_benefit = total_benefit+choice[i];
dp1[curr_node] = total+total_benefit;
}
answer_compilation[allowed] = min(dp1[0], dp2[0]);
}
ll grand_total = 0;
for (int i=0; i<(N-1); i++)
grand_total += W[i];
answer_compilation[0] = grand_total;
return answer_compilation;
}
