#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
struct State {
int cimaL, node, re;
State(int a = 0, int b = 0, int c = 0) : cimaL(a), node(b), re(c) {}
bool operator < (const State& a) const {
return (make_pair(node, make_pair(cimaL, re)) < make_pair(a.node, make_pair(a.cimaL, a.re)));
}
};
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
vector<pii> adj[MAXN];
map<State, int> dp;
int deg[MAXN];
vector<int> ans;
void calc(int node, int dad) {
int pdad = INF;
for (auto [u, w] : adj[node]) {
if (u != dad) calc(u, node);
else pdad = w;
}
for (int k = 0; k <= deg[node]; k++) {
// 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 (deg[u] <= k) {
if (dp[State(0, u, deg[u])] < dp[State(1, u, deg[u])]) {
sum0 += dp[State(0, u, deg[u])];
mini.push_back(dp[State(1, u, deg[u])] - dp[State(0, u, deg[u])]);
} else {
sum0 += dp[State(1, u, deg[u])];
r--;
}
} else {
if (dp[State(0, u, k)] < dp[State(1, u, k)]) {
sum0 += dp[State(0, u, k)];
mini.push_back(dp[State(1, u, k)] - dp[State(0, u, k)]);
} else {
sum0 += dp[State(1, u, k)];
r--;
}
}
}
sort(mini.begin(), mini.end());
int i = 0;
while (r > 0) {
sum0 += mini[i];
r--;
i++;
}
dp[State(0, node, k)] = sum0;
} else {
dp[State(0, node, k)] = 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 (deg[u] <= k) {
if (dp[State(0, u, deg[u])] < dp[State(1, u, deg[u])]) {
sum0 += dp[State(0, u, deg[u])];
mini.push_back(dp[State(1, u, deg[u])] - dp[State(0, u, deg[u])]);
} else {
sum0 += dp[State(1, u, deg[u])];
r--;
}
} else {
if (dp[State(0, u, k)] < dp[State(1, u, k)]) {
sum0 += dp[State(0, u, k)];
mini.push_back(dp[State(1, u, k)] - dp[State(0, u, k)]);
} else {
sum0 += dp[State(1, u, k)];
r--;
}
}
}
sort(mini.begin(), mini.end());
int i = 0;
while (r > 0) {
sum0 += mini[i];
r--;
i++;
}
dp[State(1, node, k)] = sum0;
} else dp[State(1, node, k)] = INF;
}
}
void dfs(int node, int dad, int mx) {
if (deg[node] <= mx) {
for (auto [u, w] : adj[node]) {
if (u != dad) dfs(u, node, mx);
}
return;
}
for (int i = mx + 1; i <= deg[node]; i++) {
ans[i] += min(dp[State(0, node, i)], dp[State(1, node, i)]);
}
mx = deg[node];
for (auto [u, w] : adj[node]) {
if (u != dad) dfs(u, node, mx);
}
}
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]});
deg[a[i]]++;
deg[b[i]]++;
}
calc(0, -1);
ans.resize(n);
dfs(0, -1, -1);
return ans;
}
