#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) a.begin(), a.end()
vector<vector<ll>> dp;
vector<vector<array<ll, 2>>> graph;
vector<bool> used;
void dfs(int n, int p, int dist, int k){
vector<array<ll, 2>> d;
for(auto x : graph[n]){
if(x[0] != p){
dfs(x[0], n, x[1], k);
d.push_back({dp[x[0]][1] - dp[x[0]][0], x[0]});
}
}
sort(all(d));
ll s1 = 0;
for (int i = 0; i != (int)d.size() and (i < (int)graph[n].size() - k or d[i][0] < 0); i++)
s1 += dp[d[i][1]][1], used[d[i][1]] = 1;
for (auto x : graph[n])
if (x[0] != p and !used[x[0]])
s1 += dp[x[0]][0];
dp[n][0] = s1;
for (int i = 0; i != (int)d.size() and (i < (int)graph[n].size() - k or d[i][0] < 0); i++)
used[d[i][1]] = 0;
if(n != 0){
s1 = 0;
for(int i = 0; i != (int)d.size() and (i < (int)graph[n].size() - k - 1 or d[i][0] < 0); i ++)
s1 += dp[d[i][1]][1], used[d[i][1]] = 1;
s1 += dist;
for(auto x : graph[n])
if(x[0] != p and !used[x[0]])
s1 += dp[x[0]][0];
dp[n][1] = s1;
for (int i = 0; i != (int)d.size() and (i < (int)graph[n].size() - k - 1 or d[i][0] < 0); i++)
used[d[i][1]] = 0;
}
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
if(count(all(u), 0) == n - 1){
vector<ll> ans(n);
for(auto x : w)
ans[0] += x;
sort(all(w), greater<int>());
for(int i = 0; i < n - 1; i ++)
ans[i + 1] = ans[i] - w[i];
return ans;
}
graph.resize(n);
for (int i = 0; i < n - 1; i++)
graph[u[i]].push_back({v[i], w[i]}), graph[v[i]].push_back({u[i], w[i]});
used.resize(n);
vector<ll> ans(n);
dp.resize(n, vector<ll> (2));
for (int i = 1; i < n; i++){
dfs(0, -1, 0, i);
ans[i] = dp[0][0];
}
for (auto x : w)
ans[0] += x;
return ans;
}
