#include "roads.h"
#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 1e5 + 5;
const int inf = 1e18;
int32_t n;
vector <pii> adj[N];
int dp[N][2]; // dp[i] = min cost for subtree i and (have/not have) edge (i, p[i])
int k = 0;
void dfs(int u, int p){
vector <int> del;
int cur = 0;
int pw = 0;
for (auto [w, v] : adj[u]) {
if (v == p) {
pw = w;
continue;
}
dfs(v, u);
del.emb(dp[v][1] - dp[v][0]);
cur += dp[v][0];
}
sort(all(del));
if (k == 1) dp[u][1] = cur;
for (int i = 0; i < del.size(); i++) {
if (del[i] > 0) break;
cur += del[i];
if (i+1 == k) dp[u][0] = cur + pw;
if (i+1 == k - 1) dp[u][1] = cur;
}
if (dp[u][0] == inf) dp[u][0] = cur + pw;
if (dp[u][1] == inf) dp[u][1] = cur;
}
std::vector<long long> minimum_closure_costs(int32_t N, std::vector<int32_t> u,
std::vector<int32_t> v,
std::vector<int32_t> w) {
n = N;
vector <int> l(n + 1), r(n + 1);
for (int32_t i = 0; i < n - 1; i++) {
u[i]++, v[i]++;
adj[u[i]].emb(w[i], v[i]);
adj[v[i]].emb(w[i], u[i]);
r[min(u[i], v[i])] = w[i];
l[max(u[i], v[i])] = w[i];
}
vector <int> ans(n);
ans[0] = accumulate(all(w), 0ll);
for (k = 1; k < n; k++) {
for (int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = inf;
dfs(1, 1);
ans[k] = dp[1][0];
// cout << k << " : \n";
// for (int i = 1; i <= n; i++) {
// cout << i << " : " << dp[i][0] << ", " << dp[i][1] << "\n";
// }
// cout << "-----------------\n";
}
return ans;
}
