#include "roads.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=100010;
int N;
vector <pll> v[mxN], ch[mxN];
vector <ll> seg[mxN], d[mxN];
int sub[mxN];
int u[mxN], dd[mxN];
void dfs0(int now, int pre)
{
sub[now]=1;
for(auto [nxt, x] : v[now]) if(nxt!=pre)
{
dfs0(nxt, now);
ch[now].emplace_back(nxt, x);
sub[now]+=sub[nxt];
}
if(ch[now].empty())
{
u[now]=dd[now]=now;
return;
}
sort(ch[now].begin(), ch[now].end(), [](pll a, pll b){return sub[a.fi]>sub[b.fi];});
dd[now]=dd[ch[now][0].fi];
u[dd[now]]=now;
}
void upd(int typ, int idx, int s1, int e1, int s2, int e2, ll val)
{
if(s1>e2 || s2>e1) return;
if(s2<=s1 && e1<=e2)
{
seg[typ][idx]+=val;
return;
}
int mid=(s1+e1)/2;
upd(typ, 2*idx, s1, mid, s2, e2, val);
upd(typ, 2*idx+1, mid+1, e1, s2, e2, val);
}
ll solv(int typ, int idx, int s, int e, int pos)
{
if(s==e) return seg[typ][idx];
int mid=(s+e)/2;
if(pos<=mid) return seg[typ][idx]+solv(typ, 2*idx, s, mid, pos);
else return seg[typ][idx]+solv(typ, 2*idx+1, mid+1, e, pos);
}
void dfs1(int now)
{
d[now].resize(ch[now].size()+1);
if(ch[now].empty())
{
seg[now].resize(4*sub[u[now]]);
return;
}
for(auto [nxt, x] : ch[now]) dfs1(nxt);
int fc=ch[now][0].fi;
u[now]=u[fc];
upd(fc, 1, 1, sub[u[fc]], sub[fc]+1, sub[now], solv(fc, 1, 1, sub[u[fc]], sub[fc]));
swap(seg[now], seg[fc]);
for(auto [nxt, x] : ch[now]) if(nxt!=fc)
{
for(int i=1;i<=sub[nxt];i++)
{
upd(now, 1, 1, sub[u[now]], i, i, solv(nxt, 1, 1, sub[nxt], i));
}
upd(now, 1, 1, sub[u[now]], sub[nxt]+1, sub[now], solv(nxt, 1, 1, sub[nxt], sub[nxt]));
}
multiset <ll> lo, hi;
vector <pll> ct;
ct=ch[now];
sort(ct.begin(), ct.end(), [](pll a, pll b){return ch[a.fi].size()>ch[b.fi].size();});
ll tsum=0;
for(auto [nxt, x] : ct) tsum+=x;
fc=ct[0].fi;
int lim=max(ch[fc].size(), ch[now].size());
upd(now, 1, 1, sub[u[now]], lim+1, sub[now], tsum);
/*for(int i=1;i<=sub[u[now]];i++)
{
printf("dp[%d][%d]=%lld\n", now, i, solv(now, 1, 1, N, i));
}*/
ll del=0;
while(ct.size() && ch[ct.back().fi].empty())
{
hi.insert(ct.back().se);
del+=ct.back().se;
ct.pop_back();
}
for(int i=1;i<=lim;i++)
{
while(hi.size()<i && lo.size())
{
hi.insert(*lo.rbegin());
del+=*lo.rbegin();
auto it=lo.end(); it--;
lo.erase(it);
}
while(hi.size()>i)
{
lo.insert(*hi.begin());
del-=*hi.begin();
hi.erase(hi.begin());
}
for(auto [nxt, x] : ct)
{
if(-d[nxt][i]+x>0)
{
hi.insert(-d[nxt][i]+x);
del+=(-d[nxt][i]+x);
}
}
vector <ll> tsh;
while(hi.size()>i)
{
tsh.push_back(*hi.begin());
del-=*hi.begin();
hi.erase(hi.begin());
}
/*printf("hi: ");
for(auto ele : hi) printf("%lld ", ele);
printf("\nlo: ");
for(auto ele : lo) printf("%lld ", ele);
printf("\n");*/
if(hi.size()==i && i<=ch[now].size()) d[now][i]=*hi.begin();
upd(now, 1, 1, sub[u[now]], i, i, del);
for(ll ele : tsh)
{
hi.insert(ele);
del+=ele;
}
for(auto [nxt, x] : ct)
{
if(-d[nxt][i]+x>0)
{
hi.erase(hi.find(-d[nxt][i]+x));
del-=(-d[nxt][i]+x);
}
}
while(ct.size() && ch[ct.back().fi].size()==i)
{
if(lo.empty() || lo.size() && ct.back().se>*lo.rbegin())
{
hi.insert(ct.back().se);
del+=ct.back().se;
}
else lo.insert(ct.back().se);
ct.pop_back();
}
}
/*for(int i=1;i<=sub[u[now]];i++)
{
printf("dp[%d][%d]=%lld\n", now, i, solv(now, 1, 1, N, i));
}*/
//printf("end %d\n", now);
}
vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
N=n;
for(int i=0;i<N-1;i++)
{
U[i]++;
V[i]++;
v[U[i]].emplace_back(V[i], W[i]);
v[V[i]].emplace_back(U[i], W[i]);
}
dfs0(1, -1);
//for(int i=1;i<=N;i++) printf("u[%d]=%d\n", i, u[i]);
dfs1(1);
//for(int i=1;i<=N;i++) for(int j=1;j<d[i].size();j++) printf("d[%d][%d]=%lld\n", i, j, d[i][j]);
vector <ll> ans;
ans.resize(N);
ll sum=0;
for(int ele : W) sum+=ele;
ans[0]=sum;
for(int i=1;i<N;i++) ans[i]=sum-solv(1, 1, 1, N, i);
return ans;
}
