#include "roads.h"
#include <functional>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
#include <assert.h>
#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 (ec[a] != ec[b]) return ec[a] > ec[b];
return a < 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<pair<int, int>> pending[2];
for (int k = N - 2; k >= 0; k--) {
used.reset();
answer[k] = answer[k + 1];
printf("===\n");
for (int i = 0; i < N; i++) {
printf("%u: ", i);
for (int c: adj[i]) printf("%u ", c);
printf("\n");
}
printf("===\n");
// 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;
// assert(partner >= 0);
// assert(adj[node].count(partner));
// assert(adj[partner].count(node));
used[node] = 1;
used[partner] = 1;
pending[0].push({node, partner});
pending[1].push({node, partner});
answer[k] += 1;
}
// printf("\n");
// printf("- ");
while (!pending[0].empty()) {
auto [origin, dest] = pending[0].top();
nodes.erase(origin);
nodes.erase(dest);
adj[origin].erase(dest);
adj[dest].erase(origin);
ec[origin]--;
ec[dest]--;
pending[0].pop();
}
while (!pending[1].empty()) {
auto [origin, dest] = pending[1].top();
if (ec[origin])
nodes.insert(origin);
if (ec[dest])
nodes.insert(dest);
pending[1].pop();
}
}
// for (int e: ec) printf("%u ", e);
// printf("\n");
return answer;
}
