#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100010;
int n, deg[N], par[N], pw[N];
ll dp[N], ep[N];
bool chk[N];
vector<int> v[N], c;
vector<pair<int, int>> st1[N], st2[N];
vector<pair<int, int>> adj[N], adj2[N];
ll sum1[N], sum2[N];
set<pair<int, int>> s1[N], s2[N];
vector<ll> ans;
void dfs0(int curr, int prev) {
for(auto [next, w]:adj[curr]) if(next!=prev) par[next]=curr, pw[next]=w, st1[curr].push_back({w, next}), dfs0(next, curr);
sort(st1[curr].rbegin(), st1[curr].rend());
st2[curr]=st1[curr];
}
void dfs(int curr, int k, bool root=false) {
dp[curr]=sum1[curr], ep[curr]=pw[curr]+sum2[curr];
for(auto [next, w]:adj2[curr]) {
dfs(next, k);
dp[curr]+=dp[next], ep[curr]+=dp[next];
}
vector<pair<int, int>> in1, in2, out1, out2;
for(auto [next, w]:adj2[curr]) {
if(ep[next]-dp[next]<0 || s1[curr].size()<=deg[curr]-k)
dp[curr]+=ep[next]-dp[next], in1.push_back({ep[next]-dp[next], next}), s1[curr].insert({ep[next]-dp[next], next});
if(s1[curr].size()>deg[curr]-k && s1[curr].rbegin()->first>0)
dp[curr]-=s1[curr].rbegin()->first, out1.push_back(*s1[curr].rbegin()), s1[curr].erase(prev(s1[curr].end()));
if(ep[next]-dp[next]<0 || s2[curr].size()<=deg[curr]-k-1)
ep[curr]+=ep[next]-dp[next], in2.push_back({ep[next]-dp[next], next}), s2[curr].insert({ep[next]-dp[next], next});
if(s2[curr].size()>deg[curr]-k-1 && s2[curr].rbegin()->first>0)
ep[curr]-=s2[curr].rbegin()->first, out2.push_back(*s2[curr].rbegin()), s2[curr].erase(prev(s2[curr].end()));
}
for(auto t:out1) s1[curr].insert(t);
for(auto t:out2) s2[curr].insert(t);
for(auto t:in1) s1[curr].erase(t);
for(auto t:in2) s2[curr].erase(t);
if(root) {
if(curr!=1) ans[k]+=min(dp[curr], ep[curr]);
else ans[k]+=dp[curr];
}
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n=N;
ans.resize(n);
for(int i=0; i<n-1; i++) {
U[i]++, V[i]++;
adj[U[i]].push_back({V[i], W[i]}), adj[V[i]].push_back({U[i], W[i]});
deg[U[i]]++, deg[V[i]]++;
}
for(int i=1; i<=n; i++) v[deg[i]].push_back(i);
dfs0(1, 0);
for(int k=n-1; k>=0; k--) {
for(int j:v[k+1]) {
adj2[par[j]].push_back({j, pw[j]});
chk[j]=true, c.push_back(j);
if(s1[par[j]].find({pw[j], j})!=s1[par[j]].end()) s1[par[j]].erase({pw[j], j}), sum1[par[j]]-=pw[j];
if(s2[par[j]].find({pw[j], j})!=s2[par[j]].end()) s2[par[j]].erase({pw[j], j}), sum2[par[j]]-=pw[j];
}
for(int j:c) {
while(s1[j].size()<deg[j]-k && !st1[j].empty()) {
pair<int, int> tmp=st1[j].back(); st1[j].pop_back();
if(chk[tmp.second]) continue;
s1[j].insert(tmp), sum1[j]+=tmp.first;
}
while(s2[j].size()<deg[j]-k-1 && !st2[j].empty()) {
pair<int, int> tmp=st2[j].back(); st2[j].pop_back();
if(chk[tmp.second]) continue;
s2[j].insert(tmp), sum2[j]+=tmp.first;
}
}
for(int j:c) if(!chk[par[j]]) dfs(j, k, true);
}
return ans;
}
