#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;
struct node {
long long sum = 0;
int cnt = 0;
};
struct segtree {
int N, rem, node_id;
vector<int> val;
vector<node> tr;
void build(int id, int lt, int rt) {
if (lt == rt) {
tr[id].sum = val[lt];
tr[id].cnt = 1;
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
tr[id].sum = tr[id * 2].sum + tr[id * 2 + 1].sum;
tr[id].cnt = tr[id * 2].cnt + tr[id * 2 + 1].cnt;
}
void init(int _node_id, vector<pair<int, int>> &pre_adj) {
node_id = _node_id;
N = pre_adj.size();
tr.resize(N * 4 + 20);
rem = N;
val.resize(N + 1);
for (int i = 1; i <= N; i++) {
val[i] = pre_adj[i - 1].first;
}
build(1, 1, N);
}
void update(int id, int lt, int rt, int pos) {
if (lt == rt) {
tr[id].sum = 0;
tr[id].cnt = 0;
return;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
update(id * 2, lt, mt, pos);
}
else {
update(id * 2 + 1, mt + 1, rt, pos);
}
tr[id].sum = tr[id * 2].sum + tr[id * 2 + 1].sum;
tr[id].cnt = tr[id * 2].cnt + tr[id * 2 + 1].cnt;
}
void update(int pos) {
pos++;
update(1, 1, N, pos);
val[pos] = 0;
rem--;
}
long long get(int id, int lt, int rt, int cnt) {
if (lt == rt) {
assert(cnt == 1);
return tr[id].sum;
}
int mt = (lt + rt) / 2;
if (tr[id * 2].cnt >= cnt) {
return get(id * 2, lt, mt, cnt);
}
else {
return tr[id * 2].sum + get(id * 2 + 1, mt + 1, rt, cnt - tr[id * 2].cnt);
}
}
long long get(int cnt) {
cnt = max(cnt, 0);
if (cnt == 0) {
return 0;
}
if (cnt > rem) {
return inf;
}
return get(1, 1, N, cnt);
}
};
vector<pair<int, int>> adj[maxN];
vector<pair<int, int>> pre_adj[maxN];
segtree tree[maxN];
vector<int> bucket[maxN];
int deg[maxN];
bool is_bad[maxN];
bool flag[maxN];
long long dp[maxN][2];
int K;
void dfs(int u, int par) {
flag[u] = true;
dp[u][0] = inf;
dp[u][1] = inf;
long long sum = 0;
vector<long long> cost;
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (v == par) {
continue;
}
dfs(v, u);
sum += dp[v][1];
cost.push_back(dp[v][0] + w - dp[v][1]);
}
sort(cost.begin(), cost.end());
int cnt = deg[u] - (par != -1);
for (int i = 0; i < 2; i++) {
dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
}
for (auto w: cost) {
sum += w;
cnt--;
for (int i = 0; i < 2; i++) {
dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
}
}
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
vector<long long> res(N);
for (int i = 0; i < N - 1; i++) {
res[0] += W[i];
pre_adj[U[i]].push_back({W[i], V[i]});
pre_adj[V[i]].push_back({W[i], U[i]});
deg[U[i]]++;
deg[V[i]]++;
}
for (int i = 0; i < N; i++) {
sort(pre_adj[i].begin(), pre_adj[i].end());
tree[i].init(i, pre_adj[i]);
bucket[deg[i]].push_back(i);
}
vector<int> bad;
for (K = N - 1; K >= 1; K--) {
for (auto u: bad) {
flag[u] = false;
}
for (auto u: bad) {
if (!flag[u]) {
dfs(u, -1);
res[K] += dp[u][0];
}
}
for (auto u: bucket[K]) {
for (auto e: pre_adj[u]) {
int v = e.second;
int w = e.first;
if (is_bad[v]) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
tree[u].update(lower_bound(pre_adj[u].begin(), pre_adj[u].end(), make_pair(w, v)) - pre_adj[u].begin());
tree[v].update(lower_bound(pre_adj[v].begin(), pre_adj[v].end(), make_pair(w, u)) - pre_adj[v].begin());
}
}
bad.push_back(u);
is_bad[u] = true;
}
}
return res;
}
