#include "roads.h"
#include <functional>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
#include <stdio.h>
using std::function;
using std::vector;
using std::bitset;
using std::stack;
using std::pair;
using std::set;
using ll = long long;
vector<long long> minimum_closure_costs(
int N, vector<int> U,
vector<int> V,
vector<int> W
) {
// vector<vector<int>> tree(N);
// {
// vector<vector<int>> adj(N);
// for (int i = 0; i < N; i++) {
// adj[U[i]].push_back(V[i]);
// adj[V[i]].push_back(U[i]);
// }
// vector<char> present(N, 0);
// function<void(int)> dfs = [&](int n) {
// for (int c: adj[n]) {
// if (present[c]) continue;
// present[c] = 1;
// tree[n].push_back(c);
// dfs(c);
// }
// };
// present[0] = 1;
// dfs(0);
// }
// vector<int> child_count(N);
// for (int i = 0; i < N; i++)
// child_count[i] = tree[i].size();
vector<int> ec(N);
for (int i = 0; i < N - 1; i++)
ec[U[i]]++, ec[V[i]]++;
auto compare = [&ec](const int& a, const int& b) -> bool {
if (a == b) return 0;
return ec[a] >= ec[b];
};
set<int, decltype(compare)> nodes(compare);
for (int i = 0; i < N; i++)
nodes.insert(i);
vector<set<int, decltype(compare)>> adj(N, set<int, decltype(compare)>(compare));
for (uint i = 0; i < N - 1; i++) {
adj[U[i]].insert(V[i]);
adj[V[i]].insert(U[i]);
}
vector<ll> answer(N, 0);
bitset<100'005> used;
stack<int> pending;
for (int k = N - 2; k >= 0; k--) {
used.reset();
answer[k] = answer[k + 1];
// printf("= ");
// for (int node: nodes) printf("%u ", node);
// printf("\n");
// printf("> ");
for (int node: nodes) {
if (used[node]) continue;
if (ec[node] <= k) break;
// printf("%u ", node);
int partner = -1;
for (auto possible_partner: adj[node]) {
if (used[possible_partner]) continue;
partner = possible_partner;
break;
}
if (partner == -1)
continue;
used[node] = 1;
used[partner] = 1;
pending.push(node);
pending.push(partner);
ec[node]--;
ec[partner]--;
answer[k] += 1;
adj[node].erase(partner);
adj[partner].erase(node);
}
// printf("\n");
// printf("- ");
while (!pending.empty()) {
int process = pending.top();
// printf("%u", process);
nodes.erase(process);
if (ec[process])
nodes.insert(process);
// else printf("-");
// printf(" ");
pending.pop();
}
// printf("\n");
}
// for (int e: ec) printf("%u ", e);
// printf("\n");
return answer;
}
