#include "roads.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long
using namespace std;
array<ll, 2> operator+(array<ll, 2> a, array<ll, 2> b) {
return {a[0]+b[0], a[1]+b[1]};
};
struct SegTree{
vector <array<ll, 2>> st;
vector <array<ll, 2>> X;
void init(ll x) {
st.resize(4*x);
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = {X[l][0], 1};
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = st[id*2] + st[id*2+1];
}
void update(ll id, ll l, ll r, ll q, array<ll, 2> w) {
if (l == r) {
st[id] = w;
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
st[id] = st[id*2] + st[id*2+1];
}
ll query(ll id, ll l, ll r, ll w) {
if (l == r) {
if (!w) return 0;
else if (st[id][1] == w) return st[id][0];
else return 1e18;
}
ll mid = (l+r)/2;
if (st[id*2][1] <= w) return st[id*2][0] + query(id*2+1, mid+1, r, w-st[id*2][1]);
else return query(id*2, l, mid, w);
}
}ST[100000];
vector <ll> A;
bool B[100000], E[100000];
ll dp[100000][2], k, f, t;
vector <ll> deg[100000];
vector <array<ll, 2>> X[100000];
map <ll, ll> mp[100000];
vector <ll> F;
vector <array<ll, 2> > adj[100000];
//0 -> only remaining k-1, 1 -> only remaining k
void dfs(ll u, ll p) {
B[u] = 1;
vector <ll> S;
ll res = 0, a = 1e18, b = 1e18, z = 0, tot = X[u].size() - (p != -1);
for (auto [v, x] : adj[u]) {
if (v == p) continue;
dfs(v, u);
res += dp[v][0];
S.push_back(dp[v][1]-dp[v][0]+x);
--tot, ++z;
}
a = min(a, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-(k-1))));
b = min(b, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-k)));
//cout << res << ":" << a << " " << b << " " << X[u].size() << " " << k << endl;
sort(S.begin(), S.end());
for (int i=0; i<S.size(); ++i) {
res += S[i];
--z;
a = min(a, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-(k-1))));
b = min(b, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-k)));
}
dp[u][0] = a, dp[u][1] = b;
//cout << u << " " << dp[u][0] << " " << dp[u][1] << endl;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
for (int i=0; i<N-1; ++i) {
X[U[i]].push_back({W[i], V[i]});
X[V[i]].push_back({W[i], U[i]});
t += W[i];
}
for (int i=0; i<N; ++i) {
sort(X[i].begin(), X[i].end(), [](auto a, auto b) {
return a[0] < b[0];
});
for (int j=0; j<X[i].size(); ++j) {
mp[i][X[i][j][1]] = j;
}
ST[i].init(X[i].size());
ST[i].X = X[i];
ST[i].build(1, 0, X[i].size()-1);
deg[X[i].size()-1].push_back(i);
}
k = N-1;
for (int i=0; i<N-1; ++i) {
f = 0;
for (auto u : deg[k]) {
E[u] = 1;
A.push_back(u);
for (auto [x, y] : X[u]) {
if (E[y]) {
adj[u].push_back({y, x});
adj[y].push_back({u, x});
ST[u].update(1, 0, ST[u].X.size()-1, mp[u][y], {0, 0});
ST[y].update(1, 0, ST[y].X.size()-1, mp[y][u], {0, 0});
}
}
}
for (auto u : A) B[u] = dp[u][0] = dp[u][1] = 0;
for (auto u : A) {
if (!B[u]) {
dfs(u, -1);
f += dp[u][1];
}
}
F.push_back(f);
--k;
}
F.push_back(t);
reverse(F.begin(), F.end());
return F;
}
