#include "roads.h"
#include <bits/stdc++.h>
#define REP(i,o,n) for(long long i=o;i<n;i++)
#define fi first
#define se second
#define pb push_back
using namespace std;
set<pair<long long,long long>> adj[200100];
set<pair<long long,long long>> child[200100];
long long sz[200100];
void dfs(long long node, long long parent=-1){
sz[node]=1;
for(auto i:adj[node]){
if(i.fi!=parent)dfs(i.fi,node),sz[node]+=sz[i.fi],child[node].insert(i);
}
}
struct ds {
multiset<long long> select, pool;
long long lim=0;
long long sum=0;
void add(long long x){
if(x<0 && select.size() < lim)select.insert(x),sum+=x;
else if(select.size() && x<0 && x < *select.rbegin())sum+=x-*select.rbegin(),pool.insert(*select.rbegin()),select.erase(select.find(*select.rbegin())),select.insert(x);
else pool.insert(x);
norm();
}
void remove(long long x){
if(pool.count(x))pool.erase(pool.find(x));
else {
select.erase(select.find(x));
sum-=x;
norm();
}
}
void norm(){
while(select.size() < lim && pool.size() && *pool.begin() < 0){
sum+=*pool.begin();
select.insert(*pool.begin());pool.erase(pool.begin());
}
while(select.size() > lim){
sum-=*select.rbegin();
pool.insert(*select.rbegin());
select.erase(select.find(*select.rbegin()));
}
}
long long query(long long q){
lim=q;
norm();
return sum;
}
};
ds store[200100];
vector<long long> dead[200100];
bool active[200100];
long long memo[200100][2];
long long bias[200100];
long long dp(long long node, long long k, bool lim){
auto &ans=memo[node][lim];
if(ans!=-1)return ans;
ans=bias[node];
long long con=k;
if(lim)con--;
vector<long long> upgrades;
for(auto i:child[node]){
ans+=dp(i.fi,k,false)+i.se;
upgrades.pb(dp(i.fi,k,true) - (dp(i.fi,k,false)+i.se));
}
for(auto i:upgrades)store[node].add(i);
// cerr<<node<<": ";
// for(auto i:store[node].select)cerr<<i<<" ";
// cerr<<"| ";
// for(auto i:store[node].pool)cerr<<i<<" ";
// cerr<<endl;
ans+=store[node].query(con);
// cerr<<">>> "<<store[node].query(con)<<" "<<ans<<endl;
for(auto i:upgrades)store[node].remove(i);
return ans;
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
std::vector<signed> V,
std::vector<signed> W) {
memset(sz,-1,sizeof sz);
memset(bias,0,sizeof bias);
REP(i,0,N)adj[i].clear(),store[i].lim=0,store[i].pool.clear(),store[i].select.clear(),store[i].sum=0,active[i]=1;
REP(i,0,N-1){
adj[U[i]].insert({V[i],W[i]});
adj[V[i]].insert({U[i],W[i]});
}
REP(i,0,N)dead[adj[i].size()+2].pb(i);
dfs(0);
set<long long> st;
REP(i,0,N+10)st.insert(i);
vector<long long> vec;
REP(i,0,N){
for(auto d:dead[i]){
for(auto a:adj[d]){
child[a.fi].erase({d,a.se});
adj[a.fi].erase({d,a.se});
store[a.fi].add(-a.se);
bias[a.fi]+=a.se;
}
st.erase(d);
}
for(auto i:st)memo[i][0]=memo[i][1]=-1;
vec.pb(dp(0,i,false));
// cerr<<endl;
}
return vec;
}
