#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
const long long INF = (long long)1e18 + 7;
const long long oo = (long long)1e15 + 7;
const int inf = (int)1e9 + 7;
int n, K, deg[N];
bool used[N];
long long dp[N][2];
vector<pair<int, int> > g[N];
bool cmp(pair<int, int> i, pair<int, int> j) {
return deg[i.first] > deg[j.first];
}
long long ans, old[N];
void dfs(int v, int pr, int last) {
for(auto [to, w] : g[v]) {
if(to == pr) {
continue;
}
dfs(to, v, w);
}
long long tot = 0;
vector<long long> cur;
for(auto [to, w] : g[v]) {
if(to == pr) {
continue;
}
tot += dp[to][1];
cur.push_back(dp[to][0]-dp[to][1]);
}
sort(cur.begin(), cur.end());
dp[v][1] = tot+last;
if(K+(v == pr)) {
dp[v][0] = tot;
for(int i = 0; i < min((int)cur.size(), K); ++i) {
if(cur[i] > oo) {
break;
}
tot += cur[i];
if(i < K+(v == pr)-1) {
dp[v][0] = min(dp[v][0], tot);
}
dp[v][1] = min(dp[v][1], tot+last);
}
} else {
dp[v][0] = INF;
}
}
void dfs(int v, int pr) {
used[v] = 1;
int i = 0;
for(auto [to, w] : g[v]) {
i++;
if(to == pr) {
continue;
}
if(deg[to] <= K) {
break;
}
if(deg[to] > K) {
dfs(to, v);
}
}
int need = max(0, deg[v]-K);
ans += need;
if(deg[v] > K && pr != -1) {
deg[pr]--;
}
}
vector<long long> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
n = _N;
bool ok = 1;
bool ko = 1;
bool kk = 1;
long long tt = 0;
for(int i = 0; i < n-1; ++i) {
int u = _U[i];
int v = _V[i];
int w = _W[i];
tt += w;
ko &= (u == 0);
ok &= (w == 1);
kk &= (u == i && v == i+1);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
if(ko) {
sort(_W.rbegin(), _W.rend());
vector<long long> sos;
for(int i = 0; i < n; ++i) {
sos.push_back(tt);
if(i < n-1) {
tt -= _W[i];
}
}
return sos;
}
if(!ok) {
vector<long long> sos;
for(int k = 0; k < n; ++k) {
if(kk && k > 2) {
sos.push_back(0);
continue;
}
K = k;
dfs(0, 0, inf);
sos.push_back(dp[0][0]);
}
return sos;
}
for(int i = 0; i < n; ++i) {
deg[i] = (int)g[i].size();
old[i] = deg[i];
}
vector<long long> po;
vector<pair<int, int> > o;
for(int i = 0; i < n; ++i) {
sort(g[i].begin(), g[i].end(), cmp);
o.push_back({deg[i], i});
}
sort(o.rbegin(), o.rend());
for(int k = 0; k < n; ++k) {
K = k;
vector<int> bad;
for(auto [x, y] : o) {
if(x <= k) {
break;
}
bad.push_back(y);
}
ans = 0;
for(auto x : bad) {
if(!used[x]) {
dfs(x, -1);
}
}
for(auto x : bad) {
deg[x] = old[x];
used[x] = 0;
}
po.push_back(ans);
}
return po;
}
