#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 110000;
struct fenwick {
vector<ll> ff;
vector<int> cc;
int n;
fenwick() {}
fenwick(int n) {
this->n = n;
ff = vector<ll>(n + 1, 0);
cc = vector<int>(n + 1, 0);
}
void upd(int k, ll x) {
for (; k <= n; k += k & -k) {
ff[k] += x;
cc[k]++;
}
}
ll _get(int k) {
ll ans = 0;
for (; k >= 1; k -= k & -k)
ans += ff[k];
return ans;
}
ll get(int k) {
int cnt = 0, pos = 0;
for (int u = (1 << 20); u > 0; u /= 2)
if (pos + u <= n && cnt + cc[pos + u] <= k) {
pos += u;
cnt += cc[pos];
}
return _get(pos);
}
};
int n, k, sh[N];
ll dp[N][2];
set<array<int, 2>> vert, g[N];
fenwick ff[N];
vector<array<int, 2>> h[N];
bool bad[N], used[N];
void rem(int v, int u, int w) {
int pos = lower_bound(begin(h[v]), end(h[v]), array<int, 2>{-w, u}) - begin(h[v]) + 1;
sh[v]++;
ff[v].upd(pos, w);
}
ll sum(int v, int t) {
t = min(t, sh[v]);
return ff[v].get(t);
}
ll dfs(int v, int p = -1) {
used[v] = true;
ll base = 0;
vector<ll> add;
for (auto [u, w] : g[v]) if (u != p) {
dfs(u, v);
dp[u][1] = max(dp[u][0], dp[u][1] + w);
base += dp[u][0];
add.push_back(dp[u][1] - dp[u][0]);
}
sort(begin(add), end(add), greater<ll>());
for (int f = 0; f < 2; f++) {
dp[v][f] = 0;
ll addsum = 0;
for (int a = 0; a <= min((int) add.size(), k - f); a++) {
int b = k - f - a;
dp[v][f] = max(dp[v][f], base + addsum + sum(v, b));
if (a < (int) add.size())
addsum += add[a];
}
}
return max(dp[v][0], dp[v][1]);
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n = N;
for (int i = 0; i < n - 1; i++) {
U[i]++; V[i]++;
g[U[i]].insert({V[i], W[i]});
g[V[i]].insert({U[i], W[i]});
}
for (int i = 1; i <= n; i++) {
vector<array<int, 2>> ch;
for (auto [u, w] : g[i])
h[i].push_back({-w, u});
sort(begin(h[i]), end(h[i]));
ff[i] = fenwick((int) g[i].size());
vert.insert({(int) g[i].size(), i});
}
ll base = 0;
vector<ll> ans;
for (k = 0; k <= n - 1; k++) {
while (!vert.empty() && (*vert.begin())[0] <= k) {
int v = (*vert.begin())[1];
vert.erase(vert.begin());
bad[v] = true;
for (auto [u, w] : g[v]) {
g[u].erase({v, w});
rem(u, v, w);
}
base += sum(v, sh[v]);
}
if (k == 0) ans.push_back(0);
else {
ll cur = base;
for (auto [s, v] : vert)
used[v] = false;
for (auto [s, v] : vert)
if (!used[v]) cur += dfs(v);
ans.push_back(cur);
}
}
ll sum = accumulate(begin(W), end(W), 0ll);
for (ll &x : ans)
x = sum - x;
return ans;
}
