#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N=1e5;
int n;
vector<vector<int>> adj[N];
int deg[N];
vector<vector<int>> edges;
bool vis[N];
ll dp[N][2];
struct Fenwick{
int n;
vector<ll> bit;
Fenwick(){}
void init(int n){
this->n=n;
bit.resize(n+1);
}
void upd(int i, int v){
i++;
while(i<=n){
bit[i]+=v;
i+=i&-i;
}
}
ll get_sum(int i){
i++;
ll ret=0;
while(i){
ret+=bit[i];
i-=i&-i;
}
return ret;
}
};
Fenwick f0[N], f1[N];
vector<int> val[N];
void dfs(int x, int k){
vis[x]=1;
vector<ll> best;
for(auto e:adj[x]){
int v=e[0];
if(deg[v]<k) break;
if(!vis[v]){
// cout << x << "->" << v << "\n";
dfs(v, k);
dp[x][0]+=dp[v][1];
dp[x][1]+=dp[v][1];
best.push_back(dp[v][0]-dp[v][1]+e[1]);
}
}
sort(best.begin(), best.end());
vector<ll> ss=best;
ss.push_back(0);
for(int i=best.size()-1; i>=0; i--){
ss[i]=ss[i+1]+best[i];
}
ll sum=0;
int cnt;
// for(int b:best) cout << b << " ";
// cout << "\n";
auto check=[&](int b, int k)->bool{
int i=lower_bound(val[x].begin(), val[x].end(), b)-val[x].begin();
cnt=f0[x].get_sum(adj[x].size()-1)-f0[x].get_sum(i-1);
int j=lower_bound(best.begin(), best.end(), b)-best.begin();
cnt+=best.size()-j;
sum=f1[x].get_sum(adj[x].size()-1)-f1[x].get_sum(i-1)+ss[j];
return cnt>=k;
};
int b=0;
for(int i=30; i>=0; i--){
if(check(b+(1<<i), k)) b+=(1<<i);
}
check(b, k);
dp[x][1]=sum-b*(cnt-k);
b=0;
for(int i=30; i>=0; i--){
if(check(b+(1<<i), k-1)) b+=(1<<i);
}
check(b, k-1);
// cout << cnt << " " << k-1 << "\n";
dp[x][0]=sum-b*(cnt-(k-1));
dp[x][0]=max(dp[x][0], 0LL);
dp[x][1]=max(dp[x][1], 0LL);
// cout << "dp[" << x << "][1] " << dp[x][1] << "\n";
// cout << "dp[" << x << "][0] " << dp[x][0] << "\n";
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n=N;
vector<ll> ret;
ll E=0;
for(int w:W) E+=w;
for(int i=0; i<n-1; i++){
edges.push_back({U[i],V[i],W[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]]++;
}
vector<vector<vector<int>>> ed(n);
map<pair<int, int>, int> ind;
for(int i=0; i<n; i++){
f0[i].init(adj[i].size());
f1[i].init(adj[i].size());
sort(adj[i].begin(), adj[i].end(), [&](vector<int> a, vector<int> b){
return a[1]<b[1];
});
for(int j=0; j<adj[i].size(); j++){
ind[{i, adj[i][j][0]}]=j;
val[i].push_back(adj[i][j][1]);
}
// cout << "val " << i << "\n";
// for(int v:val[i]) cout << v << " ";
// cout << "\n";
sort(adj[i].begin(), adj[i].end(), [&](vector<int> a, vector<int> b){
return deg[a[0]]>deg[b[0]];
});
}
for(auto e:edges){
ed[min(deg[e[1]], deg[e[0]])].push_back(e);
}
vector<int> nodes;
for(int i=0; i<n; i++) nodes.push_back(i);
for(int k=0; k<n; k++){
ll ans=0;
// cout << "k " << " " << k << "\n";
for(int x:nodes){
if(!vis[x]) dfs(x, k), ans+=dp[x][1];
}
// cout << E-ans << "\n";
ret.push_back(E-ans);
for(int x:nodes) vis[x]=0, dp[x][0]=dp[x][1]=0;
for(auto e:ed[k]){
int u=e[0], v=e[1];
for(int it=0; it<2; it++, swap(u,v)){
if(deg[u]==k){
int j=ind[{v,u}];
f1[v].upd(j, val[v][j]);
f0[v].upd(j, 1);
}
}
}
vector<int> nodes2;
for(int x:nodes){
if(deg[x]>k) nodes2.push_back(x);
}
swap(nodes, nodes2);
}
return ret;
}
// int main(){
// cin.tie(0)->sync_with_stdio(0);
// minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
// }
// nobody hears me scream
