#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 100005;
typedef long long LL;
constexpr LL INF = 1LL * 1e15;
struct muchie {
int x, y;
LL cost;
};
muchie E[NMAX];
vector <int> G[NMAX];
LL dp[NMAX][2];
LL aux[NMAX];
void Dfs (int k, int Node, int dad = -1) {
for (auto it : G[Node]) {
int to = (E[it].x == Node ? E[it].y : E[it].x);
if (to == dad) continue;
Dfs(k, to, Node);
}
for (int i = 0; i <= k; ++ i )
aux[i] = 0;
aux[0] = 0;
int grad = 0;
for (auto it : G[Node]) {
int to = (E[it].x == Node ? E[it].y : E[it].x);
if (to == dad) continue;
++ grad;
aux[grad] = aux[grad-1] + dp[to][0];
for (int cnt = min(grad-1, k); cnt >= 0; -- cnt ) {
/// elimin muchia Node -> to; NU elimin muchia Node -> to
aux[cnt] = aux[cnt] + dp[to][1];
if (cnt > 0) aux[cnt] = min(aux[cnt], aux[cnt-1] + dp[to][0]);
}
}
dp[Node][0] = INF;
dp[Node][1] = INF;
if (k > 0) dp[Node][0] = aux[min(grad, k-1)];
if (dad == -1)
dp[Node][1] = aux[min(grad, k)];
for (auto it : G[Node]) {
int to = (E[it].x == Node ? E[it].y : E[it].x);
if (to != dad) continue;
dp[Node][1] = aux[min(grad, k)] + E[it].cost;
break;
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
for (int i = 1; i < N; ++ i ) {
E[i] = {U[i-1], V[i-1], 1LL * W[i-1]};
G[U[i-1]].push_back(i);
G[V[i-1]].push_back(i);
}
vector <LL> ans;
for (int k = 0; k < N; ++ k ) {
Dfs(k, 0);
ans.push_back(dp[0][1]);
}
return ans;
}
