#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
typedef long long ll;
const int N = 100001;
int A[N], B[N], W[N], n;
vector<int> gr[N];
vector<pair<int, int>> g[N];
vector<ll> minimum_closure_costs(int nn, vector<int> uu, vector<int> vv, vector<int> ww) {
n = nn;
for (int i = 0; i < n - 1; ++i) {
A[i] = uu[i], B[i] = vv[i], W[i] = ww[i];
}
vector<ll> ans(n);
if (*max_element(all(W)) == 1) {
vector<int> pp(n), cnt(n), depth(n);
vector<bool> used(n);
function<void(int, int)> dfs = [&](int v, int p) {
pp[v] = p;
for (int to: gr[v]) {
if (to != p) {
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
};
for (int i = 0; i < n - 1; ++i) {
gr[A[i]].push_back(B[i]);
gr[B[i]].push_back(A[i]);
}
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [](int i, int j) {
return gr[i].size() > gr[j].size();
});
dfs(0, -1);
for (int k = 0; k < n; ++k) {
vector<int> now;
for (int i: ord) {
if (gr[i].size() <= k) break;
now.push_back(i);
used[i] = true;
cnt[i] = (int) gr[i].size();
}
sort(all(now), [&depth](int i, int j) {
return depth[i] > depth[j];
});
for (int i: now) {
if (pp[i] != -1 && used[pp[i]] && cnt[i] > k) {
--cnt[pp[i]];
--cnt[i];
++ans[k];
}
}
for (int i: now) {
ans[k] += max(0, cnt[i] - k);
used[i] = false;
}
}
return ans;
} else if (n <= 2000) {
for (int i = 0; i < n - 1; ++i) {
g[A[i]].emplace_back(B[i], W[i]);
g[B[i]].emplace_back(A[i], W[i]);
}
for (int k = 0; k < n; ++k) {
vector<vector<ll>> dp(n + 1, vector<ll>(2));
function<void(int, int)> dfs = [&](int v, int p) {
vector<pair<int, int>> adj;
for (auto [to, w]: g[v]) {
if (to != p) {
dfs(to, v);
adj.emplace_back(to, w);
}
}
if (k > (int) size(adj)) {
vector<ll> nw;
ll ans = 0;
for (auto [to, w]: adj) {
ans += dp[to][0] + w;
nw.push_back(dp[to][1] - dp[to][0] - w);
}
sort(all(nw));
for (int i = 0; i < (int) size(nw); ++i) {
if (nw[i] < 0)
ans += nw[i];
}
dp[v][1] = dp[v][0] = ans;
} else {
vector<ll> nw;
ll ans = 0;
for (auto [to, w]: adj) {
ans += dp[to][0] + w;
nw.push_back(dp[to][1] - dp[to][0] - w);
}
sort(all(nw));
ll added = 0;
for (int i = 0; i < k - 1; ++i) {
if (nw[i] < 0)
added += nw[i];
}
dp[v][1] = ans + added;
added = 0;
for (int i = 0; i < k; ++i) {
added += nw[i];
}
dp[v][0] = min(dp[v][1], ans + added);
}
};
dfs(0, -1);
ans[k] = dp[0][0];
}
return ans;
} else if (*max_element(all(A)) == 0) {
sort(W, W + n - 1);
ll nw = 0;
ll sum = accumulate(all(W), 0ll);
for (int k = 0; k < n; ++k) {
if (k) nw += W[n - k - 1];
ans[k] = sum - nw;
}
return ans;
} else {
for (int i = 0; i < n - 1; ++i) {
g[A[i]].emplace_back(B[i], W[i]);
g[B[i]].emplace_back(A[i], W[i]);
}
ans[0] = accumulate(all(W), 0ll);
for (int k = 1; k <= 1; ++k) {
vector<vector<ll>> dp(n + 1, vector<ll>(2));
function<void(int, int)> dfs = [&](int v, int p) {
vector<pair<int, int>> adj;
for (auto [to, w]: g[v]) {
if (to != p) {
dfs(to, v);
adj.emplace_back(to, w);
}
}
if (k > (int) size(adj)) {
vector<ll> nw;
ll ans = 0;
for (auto [to, w]: adj) {
ans += dp[to][0] + w;
nw.push_back(dp[to][1] - dp[to][0] - w);
}
sort(all(nw));
for (int i = 0; i < (int) size(nw); ++i) {
if (nw[i] < 0)
ans += nw[i];
}
dp[v][1] = dp[v][0] = ans;
} else {
vector<ll> nw;
ll ans = 0;
for (auto [to, w]: adj) {
ans += dp[to][0] + w;
nw.push_back(dp[to][1] - dp[to][0] - w);
}
sort(all(nw));
ll added = 0;
for (int i = 0; i < k - 1; ++i) {
if (nw[i] < 0)
added += nw[i];
}
dp[v][1] = ans + added;
added = 0;
for (int i = 0; i < k; ++i) {
added += nw[i];
}
dp[v][0] = min(dp[v][1], ans + added);
}
};
dfs(0, -1);
ans[k] = dp[0][0];
}
for (int k = 2; k < n; ++k) {
ans[k] = 0;
}
return ans;
}
}
