#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 dfs1(int now)
{
d[now].resize(ch[now].size()+1);
seg[now].resize(sub[now]+1);
if(ch[now].empty())
{
return;
}
for(auto [nxt, x] : ch[now]) dfs1(nxt);
for(int i=1;i<=sub[now];i++)
{
for(auto [nxt, x] : v[now])
{
if(sub[nxt]<i) seg[now][i]+=seg[nxt][sub[nxt]];
else seg[now][i]+=seg[nxt][i];
}
}
for(int i=1;i<=sub[now];i++)
{
vector <ll> pq;
for(auto [nxt, x] : ch[now])
{
if(ch[nxt].size()<i) pq.push_back(x);
else if(x-d[nxt][i]>0) pq.push_back(x-d[nxt][i]);
}
sort(pq.begin(), pq.end(), [](ll a, ll b){return a>b;});
if(i<=ch[now].size() && pq.size()>=i) d[now][i]=pq[i-1];
ll sum=0;
for(int j=0;j<min((int)pq.size(), i);j++) sum+=pq[j];
seg[now][i]+=sum;
}
}
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-seg[1][i];
return ans;
}
