#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 10;
vector<int> u, v, w;
int n;
vector<pii> T[N];
bool comp(pii i, pii j){
return w[i.se] < w[j.se];
}
struct edge{
int nex;
int oo;
int weight;
};
bool active[N];
vector<int> ad[N];
ll dp[N][2];
struct segment_tree{
vector<pii> TREE;
int sz;
void init(int nn){
sz = nn;
TREE.resize(sz * 4 + 16);
}
void add(int node, int cl, int cr, int v, int cc, ll w){
if(cl == cr){
TREE[node].fi = w;
TREE[node].se = cc;
return;
}
int mid = (cl + cr) / 2;
if(mid >= v)
add(node * 2, cl, mid, v, cc, w);
else
add(node * 2 + 1, mid + 1, cr, v, cc, w);
TREE[node].fi = TREE[node * 2].fi + TREE[node * 2 + 1].fi;
TREE[node].se = TREE[node * 2].se + TREE[node * 2 + 1].se;
}
ll get(int node, int cl, int cr, int cnt){
if(cnt == 0) return 0;
if(cl == cr){
return TREE[node].fi;
}
int mid = (cl + cr) / 2;
if(TREE[node * 2].se >= cnt){
return get(node * 2, cl, mid, cnt);
}
else{
return get(node * 2 + 1, mid + 1, cr, cnt - TREE[node * 2].se) + TREE[node * 2].fi;
}
}
};
vector<pii> F[N];
segment_tree lows[N];
int k;
bool vis[N];
void dfs(int u, ll las){
vis[u]=true;
int deg = T[u].size();
vector<ll> vals;
ll total = 0;
for(auto x : F[u]){
if(vis[x.fi]) continue;
dfs(x.fi, x.se);
total += dp[x.fi][1];
vals.push_back(dp[x.fi][0] - dp[x.fi][1]);
}
sort(vals.begin(), vals.end());
int need;
ll ash;
for(int r = 0; r <= vals.size(); r ++ ){
// take parent
need = (deg - k) - 1 - r;
ash = total + las;
if(need > 0)
ash += lows[u].get(1, 0, deg - 1, need);
if(lows[u].TREE[1].se >= need)
dp[u][0] = min(dp[u][0], ash);
// dont take parent
ash = total;
need = (deg - k) - r;
if(need > 0)
ash += lows[u].get(1, 0, deg - 1, need);
if(lows[u].TREE[1].se >= need)
dp[u][1] = min(dp[u][1], ash);
if(r < vals.size())
total += vals[r];
}
}
int L[N];
vector<ll> minimum_closure_costs(int _n, vector<int> _u,vector<int> _v, vector<int> _w) {
n = _n;
u = _u;
v = _v;
w = _w;
for(int i = 0 ; i < n - 1; i ++ ){
T[u[i]].push_back(mp(v[i], i));
T[v[i]].push_back(mp(u[i], i));
}
for(int i = 0 ; i < n; i ++ ){
ad[T[i].size()].push_back(i);
}
for(int i = 0 ; i < n; i ++ ){
sort(T[i].begin(), T[i].end(), comp);
lows[i].init(T[i].size());
for(int j = 0 ; j < T[i].size(); j ++ ){
lows[i].add(1, 0, lows[i].sz - 1, j, 1, w[T[i][j].se]);
}
}
vector<int> vse;
vector<ll> outp(n);
for(int i = n - 1; i >= 0 ; i -- ){
for(auto x : vse){
vis[x]=false;
dp[x][0]=dp[x][1]=(ll)1e18;
}
k = i;
for(auto x : vse){
if(!vis[x]){
dfs(x, 0);
outp[i] += dp[x][1];
}
}
for(auto x : ad[i]){
active[x]=true;
vse.push_back(x);
for(int j = 0; j < T[x].size(); j ++ ){
if(active[T[x][j].fi]){
F[x].push_back(mp(T[x][j].fi, w[T[x][j].se]));
F[T[x][j].fi].push_back(mp(x, w[T[x][j].se]));
lows[T[x][j].fi].add(1, 0, lows[T[x][j].fi].sz - 1, L[T[x][j].se], 0, 0);
lows[x].add(1, 0, lows[x].sz - 1, j, 0, 0);
}
else{
L[T[x][j].se] = j;
}
}
}
}
return outp;
}
