#include "roads.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
using ll = long long;
vector<pii> adj[100005], cur[100005];
vector<int> deg[100005];
ll dp[100005][2];
bool vis[100005];
struct segTree {
int n;
vector<ll> sum, val;
vector<int> ct;
void update(int i, int l, int r, int x, int v) {
if(l==r) {
sum[i] += v*val[l];
ct[i] += v;
return;
}
int m = (l+r)/2;
if(x<=m) update(i*2+1, l, m, x, v);
else update(i*2+2, m+1, r, x, v);
sum[i] = sum[i*2+1]+sum[i*2+2];
ct[i] = ct[i*2+1]+ct[i*2+2];
}
void update(int w, int v) {
int it = lower_bound(val.begin(), val.end(), w)-val.begin();
update(0, 0, n-1, it, v);
}
void build(vector<ll> &v) {
val = v;
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end())-val.begin());
n = val.size();
sum.resize(4*n+1, 0);
ct.resize(4*n+1, 0);
for(int vv:v) update(vv, 1);
}
int find(int i, int l, int r, int x) {
if(ct[i]<x) return 2e9;
if(l==r) {
if(ct[i]>=x) return val[l];
return 2e9;
}
int m = (l+r)/2;
if(ct[i*2+1]>=x) return find(i*2+1, l, m, x);
else return find(i*2+2, m+1, r, x-ct[i*2+1]);
}
int find(int x) {
return find(0, 0, n-1, x);
}
ll findsum(int i, int l, int r, int x) {
if(ct[i]<=x) return sum[i];
if(x==0) return 0;
if(l==r) {
if(ct[i]>=x) return x*val[l];
return sum[i];
}
int m = (l+r)/2;
if(ct[i*2+1]>=x) return findsum(i*2+1, l, m, x);
else return findsum(i*2+1, l, m, x)+findsum(i*2+2, m+1, r, x-ct[i*2+1]);
}
ll findsum(int x) {
return findsum(0, 0, n-1, x);
}
};
vector<segTree> t;
void dfs(int u, int p, int wp, int mx) {
vis[u] = 1;
dp[u][0] = 0;
dp[u][1] = wp;
for(int j=0;j<2;j++) {
int ct = adj[u].size()-mx-j;
vector<ll> add;
for(auto [v, w]:cur[u]) {
if(v==p) continue;
if(!vis[v]) dfs(v, u, w, mx);
dp[u][j] += min(dp[v][0], dp[v][1]);
if(dp[v][1]<dp[v][0]) ct--;
else add.push_back(dp[v][1]-dp[v][0]);
}
if(ct<=0) continue;
sort(add.begin(), add.end());
for(int i=0; i<add.size() && ct; i++) {
if(add[i]<t[u].find(ct)) {
dp[u][j] += add[i];
ct--;
} else {
break;
}
}
if(ct) dp[u][j] += t[u].findsum(ct);
}
}
vector<long long> 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[adj[i].size()-1].push_back(i);
}
vector<int> nodes;
vector<long long> ans(n, 0);
t.resize(n);
for(int i=0;i<n;i++) {
vector<ll> val;
for(auto [v, w]:adj[i]) val.push_back((ll)w);
t[i].build(val);
}
for(int i=n-1;i>=0;i--) {
for(int u:deg[i]) {
for(auto [v, w]:adj[u]) {
cur[v].push_back({u, w});
t[v].update(w, -1);
}
nodes.push_back(u);
}
for(int u:nodes) {
if(vis[u]) continue;
dfs(u, -1, 0, i);
ans[i] += dp[u][0];
}
for(int u:nodes) {
vis[u] = 0;
}
}
return ans;
}
