#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> inside;
ll cost = 0;
int required = 0;
void insert(int T, int NT) {
if(T == -1 && NT == -1) return;
//if(flag == 1) cerr << " + " << T << ' ' << NT << '\n';
inside.emplace(T - NT, NT);
}
void gerer() { // doar fa un treap in pula mea
;
}
void cut() {
required++;
}
void erase(int T, int NT) {
if(T == -1 && NT == -1) return;
//if(flag == 1) cerr << " - " << T << ' ' << NT << '\n';
inside.erase(inside.find(pii{T - NT, NT}));
return;
}
pii query() {
ll sum = 0;
for(auto [a, b] : inside) sum += b;
//if(flag == 1) cerr << sum << '\t';
auto it = inside.begin();
int timer = 0;
while(timer < required || (it != inside.end() && it -> first < 0)) timer++, sum += it -> first, it = next(it);
//if(flag == 1) cerr << sum << ", " << timer << '\n';
cost = sum;
auto dual = cost;
if(timer == required) dual += it -> first;
return pii{cost, dual};
}
};
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();
//if(flag == 1)
//cerr << node << ' ' << f << ' ' << f_w << ' ' << RNT << ' ' << RT + f_w << '\n';
for(auto [x, y] : TNT)
inward[node].erase(x, y);
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--) {
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
