#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
vector<int> id(n - 1);
set<pair<int, int>> e1, e2;
vector<int> d(n);
for (int i = 0; i + 1 < n; i++) {
++d[u[i]];
++d[v[i]];
}
for (int i = 0; i + 1 < n; i++) {
e1.insert({min(d[u[i]], d[v[i]]), i});
e2.insert({max(d[u[i]], d[v[i]]), i});
}
vector<long long> ans(n);
for (int k = n - 1; k >= 0; k--) {
if (k < n - 1) ans[k] = ans[k + 1];
while (true) {
auto [x, y] = *e1.rbegin();
if (x <= k) break;
e1.erase(--e1.end());
e2.erase({max(d[u[y]], d[v[y]]), y});
--d[u[y]];
--d[v[y]];
++ans[k];
e1.insert({min(d[u[y]], d[v[y]]), y});
e2.insert({max(d[u[y]], d[v[y]]), y});
}
while (true) {
auto [x, y] = *e2.rbegin();
if (x <= k) break;
e2.erase(--e2.end());
e1.erase({min(d[u[y]], d[v[y]]), y});
--d[u[y]];
--d[v[y]];
++ans[k];
e1.insert({min(d[u[y]], d[v[y]]), y});
e2.insert({max(d[u[y]], d[v[y]]), y});
}
}
return ans;
}
