#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<ll,ll>
#define fi first
#define se second
const ll INF=1000000000;
const ll K=200000;
ll seg[4*K]={};
ll lazy[4*K]={};
void Build(ll l,ll r,ll pos){
if(l==r){
seg[pos]=0;
lazy[pos]=INF;
return;
}
ll m=(l+r)/2;
Build(l,m,2*pos);
Build(m+1,r,2*pos+1);
seg[pos]=seg[2*pos]+seg[2*pos+1];
lazy[pos]=INF;
}
void UpdateLazy(ll l,ll r,ll pos){
if(lazy[pos]==INF) return;
seg[pos]=(r-l+1LL)*lazy[pos];
if(l!=r){
lazy[2*pos]=lazy[pos];
lazy[2*pos+1]=lazy[pos];
}
lazy[pos]=INF;
}
void Update(ll l,ll r,ll pos,ll ql,ll qr,ll qval){
if(ql>qr) return;
UpdateLazy(l,r,pos);
if(ql>r || qr<l) return;
if(ql<=l && qr>=r){
lazy[pos]=qval;
UpdateLazy(l,r,pos);
return;
}
ll m=(l+r)/2;
Update(l,m,2*pos,ql,qr,qval);
Update(m+1,r,2*pos+1,ql,qr,qval);
seg[pos]=(seg[2*pos]+seg[2*pos+1]);
}
ll Query(ll l,ll r,ll pos, ll ql,ll qr){
if(ql>qr) return 0;
UpdateLazy(l,r,pos);
if(ql>r || qr<l) return 0;
if(ql<=l && qr>=r){
return seg[pos];
}
ll m=(l+r)/2;
return (Query(l,m,2*pos,ql,qr)+Query(m+1,r,2*pos+1,ql,qr));
}
const ll N=100000;
vector<pii> edges[N];
vector<ll> et;
ll n,m;
ll deg[N];
ll depth[N];
ll focc[N];
ll locc[N];
ll parent[N];
ll upweight[N];
void euler_tour(ll u,ll p){
parent[u]=p;
focc[u]=et.size();
et.push_back(u);
for(auto v:edges[u]){
if(v.fi==p) continue;
depth[v.fi]=depth[u]+1;
upweight[v.fi]=v.se;
euler_tour(v.fi,u);
et.push_back(u);
}
locc[u]=et.size()-1;
}
vector<ll> bydeg[N];
multiset<ll> allnums[N];
multiset<ll> topk[N];
multiset<ll> topk1[N];
ll dp[N];
ll dp1[N];
void dfs(ll u,ll p){
dp[u]=dp1[u]=0;
for(auto v:edges[u]){
if(v.fi==p) continue;
dfs(v.fi,u);
allnums[u].insert(upweight[v.fi]+dp1[v.fi]-dp[v.fi]);
dp[u]+=dp[v.fi];
dp1[u]+=dp[v.fi];
}
auto it=allnums[u].end();
if(it!=allnums[u].begin()){
it--;
topk[u].insert(*it);
dp[u]+=max(*it,0LL);
allnums[u].erase(it);
}
}
ll k=2;
void updatepp(){
vector<pii> needupdate;
for(ll i:bydeg[k]) needupdate.push_back(mp(depth[i],i));
for(ll i:bydeg[k]){
if(i==0) continue;
if(deg[parent[i]]>=k) continue;
needupdate.push_back(mp(depth[parent[i]],parent[i]));
}
sort(needupdate.begin(),needupdate.end(),greater<pii>());
for(auto pa:needupdate){
ll u=pa.se;
ll orval=dp[u];
ll orval1=dp1[u];
if(topk1[u].size()!=topk[u].size()){
dp1[u]+=max(*topk[u].begin(),0LL);
topk1[u].insert(*topk[u].begin());
}
if(!allnums[u].empty()){
auto it=allnums[u].end();
it--;
dp[u]+=max(*it,0LL);
topk[u].insert(*it);
allnums[u].erase(it);
}
ll ex=Query(0,m-1,1,focc[u],locc[u]);
dp[u]+=ex;
dp1[u]+=ex;
if(u==0) continue;
if(deg[u]<k){
Update(0,m-1,1,focc[u],locc[u],0);
Update(0,m-1,1,focc[u],focc[u],dp[u]-orval);
} else{
ll p=parent[u];
ll val=upweight[u]+orval1-orval;
bool w=false;
bool w1=false;
if(topk1[p].find(val)!=topk1[p].end()){
topk[p].erase(topk[p].find(val));
topk1[p].erase(topk1[p].find(val));
dp[p]-=max(val,0LL);
dp1[p]-=max(val,0LL);
} else if(topk[p].find(val)!=topk[p].end()){
topk[p].erase(topk[p].find(val));
dp[p]-=max(val,0LL);
} else{
allnums[p].erase(allnums[p].find(val));
}
val=upweight[u]+dp1[u]-dp[u];
topk[p].insert(val);
dp[p]+=max(val,0LL);
topk1[p].insert(val);
dp1[p]+=max(val,0LL);
if(topk[p].size()>=k){
auto it=topk[p].begin();
allnums[p].insert(*it);
dp[p]-=max(*it,0LL);
topk[p].erase(it);
}
if(topk1[p].size()>=k-1){
dp1[p]-=max(*topk1[p].begin(),0LL);
topk1[p].erase(topk1[p].begin());
}
}
}
Update(0,m-1,1,0,n-1,0);
k++;
}
vector<ll> minimum_closure_costs(int nn,vector<int> u,vector<int> v,vector<int> w){
n=nn;
ll tot=0;
for(ll i=0;i<n-1;i++){
edges[u[i]].push_back(mp(v[i],w[i]));
edges[v[i]].push_back(mp(u[i],w[i]));
deg[u[i]]++,deg[v[i]]++;
tot+=w[i];
}
depth[0]=0;
euler_tour(0,-1);
m=et.size();
vector<ll> ans;
ans.push_back(tot);
dfs(0,-1);
ans.push_back(tot-dp[0]);
for(ll i=0;i<n;i++){
for(ll j=0;j<=deg[i];j++) bydeg[j].push_back(i);
}
Build(0,m-1,1);
while(k<n){
updatepp();
ans.push_back(tot-dp[0]);
}
return ans;
}
