#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "roads.h"
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
const int N = 100'005;
vector<array<int, 2>> adj[N];
ll dp[N][2];
int deg[N];
vector<int> order;
array<ll, 2> par[N];
void build(int i, int p) {
vector<array<int, 2>> newadj;
for (auto [nxt, w] : adj[i]) {
if (nxt == p) continue;
build(nxt, i);
par[nxt] = {i, w};
newadj.push_back({nxt, w});
}
adj[i] = newadj;
order.push_back(i);
}
priority_queue<ll> taken[N];
ll sum[N];
priority_queue<ll, vector<ll>, greater<ll>> pending[N];
vector<int> rem[N];
bool in[N];
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < n - 1; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
for (int i = 0; i < n; i++) {
deg[i] = adj[i].size();
rem[deg[i]].push_back(i);
in[i] = 1;
}
build(0, -1);
par[0] = {0, (int)1e18};
vector<ll> ret(n, 0);
for (int m = 0; m < n; m++) {
for (auto i : rem[m]) {
in[i] = 0;
if (par[i][0] != i) {
int p = par[i][0], w = par[i][1];
pending[p].push(w);
// cout << "+ " << p << ' ' << w << '\n';
while (taken[p].size() && pending[p].top() < taken[p].top()) {
ll x = taken[p].top();
ll y = pending[p].top();
taken[p].pop();
sum[p] -= x;
pending[p].pop();
taken[p].push(y);
sum[p] += y;
pending[p].push(x);
// cout << "- " << p << ' ' << y << '\n';
// cout << "+ " << p << ' ' << x << '\n';
}
}
for (auto [nxt, w] : adj[i]) {
par[nxt][0] = nxt;
}
}
vector<int> neworder;
for (auto i : order) {
if (!in[i]) continue;
neworder.push_back(i);
// dp[i][1] = 0;
// dp[i][0] = par[i][1];
vector<ll> vals;
vector<array<int, 2>> newadj;
ll ttl = 0;
for (auto [nxt, w] : adj[i]) {
if (!in[nxt]) continue;
newadj.push_back({nxt, w});
// if (i == 0) {
// cout << ">>> " << nxt << ' ' << dp[nxt][1] << '\n';
// }
ttl += dp[nxt][1];
vals.push_back(dp[nxt][0] - dp[nxt][1]);
}
adj[i] = newadj;
sort(vals.begin(), vals.end());
int cnt = max(0, deg[i] - m - 1);
int sz = max(0, cnt - SZ(vals));
while (SZ(taken[i]) > sz) {
ll x = taken[i].top();
taken[i].pop();
sum[i] -= x;
pending[i].push(x);
}
while (SZ(taken[i]) < sz && SZ(pending[i])) {
ll x = pending[i].top();
pending[i].pop();
taken[i].push(x);
sum[i] += x;
}
ll s = par[i][1] + ttl;
for (int j = 0; j < cnt - SZ(taken[i]); j++) {
s += vals[j];
}
dp[i][0] = s + sum[i];
vector<ll> torem;
for (int j = cnt - SZ(taken[i]) - 1; j >= 0; j--) {
if (pending[i].empty()) break;
torem.push_back(pending[i].top());
pending[i].pop();
taken[i].push(torem.back());
sum[i] += torem.back();
s -= vals[j];
dp[i][0] = min(dp[i][0], s + sum[i]);
}
// if (m == 1 && i == 1) {
// cout << SZ(pending[i]) << endl;
// }
while (SZ(torem)) {
ll x = torem.back();
torem.pop_back();
assert(x == taken[i].top());
taken[i].pop();
sum[i] -= x;
pending[i].push(x);
}
torem.clear();
cnt = max(0, deg[i] - m);
if (i != 0 && cnt == deg[i]) {
dp[i][1] = 1e18;
} else {
sz = max(0, cnt - SZ(vals));
while (SZ(taken[i]) < sz && SZ(pending[i])) {
ll x = pending[i].top();
pending[i].pop();
// if (i == 0) {
// cout << ">> " << pending[i].top() << '\n';
// }
taken[i].push(x);
sum[i] += x;
torem.push_back(x);
}
// if (m == 1 && i == 0) {
// cout << deg[i] << ' ' << SZ(vals) << ' ' << SZ(pending[i]) << ' ' << SZ(taken[i]) << endl;
// }
s = ttl;
for (int j = 0; j < cnt - SZ(taken[i]); j++) {
s += vals[j];
}
dp[i][1] = s + sum[i];
for (int j = cnt - SZ(taken[i]) - 1; j >= 0; j--) {
if (pending[i].empty()) break;
torem.push_back(pending[i].top());
pending[i].pop();
taken[i].push(torem.back());
sum[i] += torem.back();
s -= vals[j];
// if (i == 0) {
// cout << "- " << vals[j] << '\n';
// cout << "+ " << torem.back() << '\n';
// }
dp[i][1] = min(dp[i][1], s + sum[i]);
}
// if (i == 0) {
// cout << "> " << ttl << ' ' << sum[i] << ' ' << min(cnt, SZ(vals)) << ' ' << sz << '\n';
// cout << dp[i][1] << '\n';
// }
while (SZ(torem)) {
ll x = torem.back();
torem.pop_back();
assert(x == taken[i].top());
taken[i].pop();
sum[i] -= x;
pending[i].push(x);
}
torem.clear();
// for (int j = 0; j < cnt; j++) {
// dp[i][1] += vals[j];
// }
}
dp[i][1] = min(dp[i][1], dp[i][0]);
// cout << i << ": " << dp[i][0] << ' ' << dp[i][1] << '\n';
if (par[i][0] == i) {
ret[m] += dp[i][1];
}
}
order = neworder;
// for (auto i : order) {
// cout << i << ' ';
// }
// cout << "\n\n";
// ret[m] = dp[0][1];
}
return ret;
}
