#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
int k;
vector<long long> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W) {
// N^2 solution
vector<vector<pair<int,int>>> edges;
vector<long long> ans(N,0);
edges.resize(N);
for(int i = 0;i < N-1;i++){
edges[U[i]].push_back({V[i],W[i]});
edges[V[i]].push_back({U[i],W[i]});
}
vector<int> sv(N);
iota(sv.begin(),sv.end(),0);
sort(sv.begin(),sv.end(),[&](auto a,auto b){
return edges[a].size() > edges[b].size();
});
for(auto &i:edges){
sort(i.begin(),i.end(),[&](auto a,auto b){
return edges[a.first].size() > edges[b.first].size();
});
}
// for(auto i:edges){
// for(auto j:i)cout << j.first << " ";cout << endl;
// }cout << endl;
ans[0] = N-1;
vector<bool> vis(N,true);
vector<int> deg(N);
for(int k = 1;k < N;k++){
for(auto v:sv){
if(edges[v].size() <= k)break;
vis[v] = false;
deg[v] = edges[v].size();
}
function<void(int,int)> dfs = [&](int cur,int p){
vis[cur] = true;
for(auto [nxt,w]:edges[cur]){
if(edges[nxt].size() <= k)break;
if(nxt == p)continue;
dfs(nxt,cur);
}
ans[k] += max(0,deg[cur]-k);
if(p != -1 && deg[cur] > k){
deg[p]--;
}
};
// cout << k << ":" << endl;
for(auto v:sv){
if(edges[v].size() <= k)break;
if(vis[v])continue;
dfs(v,-1);
}
// cout << endl;
}
return ans;
}
// // grader
// #include "roads.h"
// #include <cassert>
// #include <cstdio>
// #include <vector>
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> U(N - 1), V(N - 1), W(N - 1);
// for (int i = 0; i < N - 1; ++i) {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
// std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
// for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%lld",closure_costs[i]);
// }
// printf("\n");
// return 0;
// }
