#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
vector<pii> adj[MAXN];
int dp[2][MAXN];
int k;
void dfs(int node, int dad) {
int pdad = INF;
for (auto [u, w] : adj[node]) {
if (u != dad) dfs(u, node);
else pdad = w;
}
// calc dp[0][node] -> edge {node, dad} isn't removed
if ((k > 0) || (node == 0)) {
int r = (((int) adj[node].size()) - k);
vector<int> mini;
int sum0 = 0;
for (auto [u, w] : adj[node]) {
if (u == dad) continue;
if (dp[0][u] < dp[1][u]) {
sum0 += dp[0][u];
mini.push_back(dp[1][u] - dp[0][u]);
} else {
sum0 += dp[1][u];
r--;
}
}
sort(mini.begin(), mini.end());
int i = 0;
while (r > 0) {
sum0 += mini[i];
r--;
i++;
}
dp[0][node] = sum0;
} else {
dp[0][node] = INF;
}
// calc dp[1][node] -> edge {node, dad} is removed
if (node != 0) {
int r = (((int) adj[node].size()) - k - 1);
vector<int> mini;
int sum0 = pdad;
for (auto [u, w] : adj[node]) {
if (u == dad) continue;
if (dp[0][u] < dp[1][u]) {
sum0 += dp[0][u];
mini.push_back(dp[1][u] - dp[0][u]);
} else {
sum0 += dp[1][u];
r--;
}
}
sort(mini.begin(), mini.end());
int i = 0;
while (r > 0) {
sum0 += mini[i];
r--;
i++;
}
dp[1][node] = sum0;
} else dp[1][node] = INF;
}
vector<int> minimum_closure_costs(int32_t n, vector<int32_t> a, vector<int32_t> b, vector<int32_t> w) {
for (int i = 0; i < (n - 1); i++) {
adj[a[i]].push_back({b[i], w[i]});
adj[b[i]].push_back({a[i], w[i]});
}
vector<int> ans(n);
for (int i = 0; i < 2; i++) {
k = i;
dfs(0, -1);
ans[i] = min(dp[0][0], dp[1][0]);
}
return ans;
}
