#include "roads.h"
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
typedef long long ll;
struct fenwick {
vector<ll> t;
int n;
fenwick() = default;
fenwick(int x) {
n = x + 1;
t.assign(n, 0);
}
void init(int x) {
n = x + 1;
t.assign(n, 0);
}
void add(int i, int x) {
i += 1;
for (; i < n; i += i & -i)
t[i] += x;
}
ll get(int i) {
ll ans = 0;
i += 1;
i = min(n - 1, i);
for (; i > 0; i -= i & -i)
ans += t[i];
return ans;
}
int kth(int k) {
if (k == 0) return -1;
int i = 0;
for (int j = 18; j > -1; --j) {
if (i + (1 << j) < n && t[i + (1 << j)] < k) {
i += (1 << j);
k -= t[i];
}
}
return i;
}
};
const int N = 100001;
int A[N], B[N], W[N], n, par[N], sz[N], wp[N], depth[N];
vector<pair<int, int>> g[N], gr[N];
fenwick f1[N], f2[N];
bool used[N];
ll dp[2][N], sm[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; ++i) {
gr[i].clear(), g[i].clear();
sm[i] = 0;
}
for (int i = 0; i < n - 1; ++i) {
A[i] = uu[i], B[i] = vv[i], W[i] = ww[i];
gr[A[i]].emplace_back(-W[i], B[i]);
gr[B[i]].emplace_back(-W[i], A[i]);
}
for (int i = 0; i < n; ++i) {
sort(all(gr[i]));
sz[i] = (int) size(gr[i]);
f1[i].init(sz[i]);
f2[i].init(sz[i]);
}
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [](int i, int j) {
return sz[i] > sz[j];
});
function<void(int, int, int)> prec = [&prec](int v, int p, int wep) {
par[v] = p;
wp[v] = wep;
for (auto [w, to]: gr[v]) {
if (to != p) {
depth[to] = depth[v] + 1;
prec(to, v, -w);
}
}
};
vector<ll> ans(n);
prec(0, -1, 0);
for (int k = 0; k < n; ++k) {
vector<int> now;
for (int i: ord) {
if (sz[i] < k) break;
if (sz[i] == k) {
for (auto [w, to]: gr[i]) {
if (sz[to] <= sz[i]) continue;
int id = lower_bound(all(gr[to]), make_pair(w, i)) - begin(gr[to]);
assert(id < sz[to] && gr[to][id] == make_pair(w, i));
f1[to].add(id, 1);
f2[to].add(id, -w);
sm[to] += -w;
}
continue;
}
now.push_back(i);
used[i] = true;
}
for (int x: now) {
if (par[x] != -1 && used[par[x]]) {
g[par[x]].emplace_back(x, wp[x]);
}
}
const ll infL = 3e18;
for (int x: now) used[x] = false;
function<void(int, int)> dfs = [&](int v, int p) {
used[v] = true;
vector<pair<int, int>> adj;
for (auto [to, w]: g[v]) {
if (to != p) {
dfs(to, v);
adj.emplace_back(to, w);
}
}
vector<ll> nw;
ll sum = 0;
for (auto [to, w]: adj) {
nw.push_back(dp[1][to] - dp[0][to] - w);
sum += dp[0][to] + w;
}
sort(all(nw));
dp[1][v] = dp[0][v] = infL;
for (int take = 0; take <= min(k, (int) size(nw)); ++take) {
if (take) {
sum += nw[take - 1];
}
if (take < k) {
int id = f1[v].kth(k - take - 1);
ll added = sm[v] - f2[v].get(id);
dp[1][v] = min(dp[1][v], sum + added);
}
int id = f1[v].kth(k - take);
ll added = sm[v] - f2[v].get(id);
dp[0][v] = min(dp[0][v], sum + added);
}
dp[0][v] = min(dp[0][v], dp[1][v]);
};
sort(all(now), [](int i, int j) {
return depth[i] < depth[j];
});
for (int v: now) {
if (!used[v]) {
dfs(v, -1);
assert(dp[0][v] != infL);
ans[k] += dp[0][v];
}
}
for (int v: now) {
used[v] = false;
g[v].clear();
}
}
return ans;
}
