#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 250'005;
using ll = long long;
const ll inf = 1e18;
template <typename T>
struct fenwick {
vector<T> fenw;
vector<int> cnt;
int n;
fenwick() { }
fenwick(int _n) : n(_n) {
fenw.resize(n + 1);
cnt.resize(n + 1);
}
void modify(int x, T v) {
while (x <= n) {
fenw[x] += v;
cnt[x]++;
x += x & (-x);
}
}
T get(int x) {
T v{};
while (x > 0) {
v += fenw[x];
x -= x & (-x);
}
return v;
}
T query(int v) {
if (v == 0) return 0;
int idx = 0;
for (int i = 19; i >= 0; i--) {
if (idx + (1 << i) <= n && v > cnt[idx + (1 << i)]) {
v -= cnt[idx + (1 << i)];
idx += (1 << i);
}
}
if (idx == n) return inf;
idx++;
return get(idx);
}
};
fenwick<ll> ds[mxN];
int deg[mxN];
set<pair<int, int>> ad[mxN];
vector<int> deg_nodes[mxN];
set<int> nodes;
int n;
bool vis[mxN];
int K;
pair<ll, ll> dfs(int u) {
vis[u] = true;
priority_queue<ll> pq;
int childs = 0;
ll r1 = inf, r2 = inf;
__int128 cur = 0;
for (auto [v, w] : ad[u]) {
if (vis[v]) continue;
childs++;
auto [d1, d2] = dfs(v);
cur += d1;
pq.push(d1 - d2 - w);
}
for (int take = 0; take <= childs; take++) {
if (take > 0) {
cur -= pq.top();
pq.pop();
}
if (cur > inf) continue;
r1 = min(r1, (long long) cur + ds[u].query(max(0, deg[u] - K - take)));
r2 = min(r2, (long long) cur + ds[u].query(max(0, deg[u] - K - 1 - take)));
}
r1 = min(r1, inf);
r2 = min(r2, inf);
return {r1, r2};
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n = N;
for (int i = 0; i < n; i++) nodes.insert(i);
for (int i = 0; i < n - 1; i++) {
int u = U[i], v = V[i], w = W[i];
ad[u].insert({v, w});
ad[v].insert({u, w});
deg[u]++, deg[v]++;
}
vector<pair<int, int>> weight[n];
for (int i = 0; i < n; i++) {
deg_nodes[deg[i]].push_back(i);
weight[i].push_back({-1, -1});
for (auto [v, w] : ad[i]) weight[i].push_back({w, v});
sort(weight[i].begin(), weight[i].end());
ds[i] = fenwick<long long> (deg[i]);
}
vector<long long> ans(n);
for (int k = 0; k < n; k++) {
K = k;
for (int u : nodes) {
if (!vis[u]) {
ans[k] += dfs(u).first;
}
}
for (int u : nodes) {
vis[u] = false;
}
for (int u : deg_nodes[k]) {
nodes.erase(u);
for (auto [v, w] : ad[u]) {
if (!nodes.count(v)) continue;
ad[v].erase({u, w});
int idx = lower_bound(weight[v].begin(), weight[v].end(), make_pair(w, u)) - weight[v].begin();
ds[v].modify(idx, w);
}
}
}
return ans;
}
