#include "roads.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<ll,ll>;
using tii = tuple<int,int,int>;
const int nmax = 1e5 + 5;
int occ[nmax], flag;
struct Sons {
multiset<pii> active, inactive;
ll cost = 0;
int required = 0;
void insert(int T, int NT) {
if(T == -1 && NT == -1) return;
if(T <= NT) {
cost += T;
active.emplace(T - NT, NT);
}
else {
inactive.emplace(T - NT, NT);
cost += NT;
}
}
void gerer() { // doar fa un treap in pula mea
while(sz(active) < required && sz(inactive)) {
auto [a, b] = *inactive.begin();
inactive.erase(inactive.begin());
cost += a;
active.emplace(a, b);
}
while(sz(active) && active.rbegin() -> first > 0 && sz(active) > required) {
auto [a, b] = *active.rbegin();
cost -= a;
active.erase(active.find(pii{a, b}));
inactive.emplace(a, b);
}
while(sz(active) && sz(inactive) && active.rbegin() -> first > inactive.begin() -> first) {
auto [a, b] = *active.rbegin();
auto [c, d] = *inactive.begin();
cost -= a;
cost += c;
active.erase(active.find(pii{a, b}));
inactive.erase(inactive.find(pii{c, d}));
active.emplace(c, d);
inactive.emplace(a, b);
}
}
void cut() {
required++;
}
void erase(int T, int NT) {
if(T == -1 && NT == -1) return;
T -= NT;
if(active.count(pii{T, NT})) {
active.erase(active.find(pii{T, NT}));
cost -= T, cost -= NT;
}
else {
cost -= NT;
inactive.erase(inactive.find(pii{T, NT}));
}
return;
}
pii query() {
gerer();
//if(flag == 3)
//cerr << (sz(active)? active.rbegin() -> first : -1) << ' ' << (sz(inactive)? inactive.begin() -> first : -1) << '\n';
if(required + 1 <= sz(active)) return pii{cost, cost};
auto [a, b] = *inactive.begin();
return pii{cost, cost + a};
}
};
vector<pii> g[nmax];
vector<pii> t[nmax];
int N;
vector<int> incepe[nmax];
Sons inward[nmax];
pii dfs(int node, int f, int f_w) {
occ[node] = flag;
vector<pii> TNT;
for(auto [a, w] : t[node]) {
if(a == f) continue;
auto [st, snt] = dfs(a, node, w);
TNT.emplace_back(st, snt);
inward[node].insert(st, snt);
}
auto [RT, RNT] = inward[node].query();
for(auto [x, y] : TNT)
inward[node].erase(x, y);
//cerr << node << ": " << RT + f_w << ' ' << RNT << '\n';
return pii{RT + f_w, RNT};
}
std::vector<long long> minimum_closure_costs(signed N_, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
N = N_;
ll sum = 0;
for(int i = 0; i < sz(U); i++) {
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
sum += W[i];
}
vector<ll> rez(N);
rez[0] = sum;
for(int i = 0; i < N; i++) {
incepe[sz(g[i]) - 1].emplace_back(i);
}
vector<int> withme;
for(int i = N - 1; i > 0; i--) {
//cerr << "---------\n";
for(auto x: incepe[i]) {
for(auto [a, b] : g[x]) {
if(sz(g[a]) < sz(g[x])) inward[x].insert(b, 0);
else {
if(sz(g[a]) > sz(g[x]) || (sz(g[a]) == sz(g[x]) && a > x))
t[x].emplace_back(a, b),
t[a].emplace_back(x, b);
if(sz(g[a]) > sz(g[x]))
inward[a].erase(b, 0);
}
}
withme.emplace_back(x);
}
if(sz(withme) > 0) {
//for(auto x : withme) cerr << x << ' ';
//cerr << "\n--\n";
flag++;
for(auto x : withme) {
if(occ[x] != flag)
rez[i] += dfs(x, x, 0).second;
}
for(auto x : withme)
inward[x].cut();
}
//cerr << rez[i] << '\n';
}
return rez;
}
#undef int
//101308465+
//22623807+
//229740165
