#include "roads.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const lli INF = 1e17;
const lli MX = 1e9 + 5;
const int M = 1e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q,k;
vector<int> deg(M, 0);
vector<array<int,2> > p(M);
vector<vector<array<int,2> > > adj(M, vector<array<int,2> >());
vector<array<int,2> > deg_nodes;
vector<int> tin(M, 0), vis(M, -1);
int timer = 0;
set<array<int,2> > roots;
struct Node {
int sz;
lli sum;
int lc, rc;
Node() : sz(0), sum(0ll), lc(-1), rc(-1) {};
};
struct SegT {
vector<Node> data;
int sz;
int nxt = 1;
SegT() : sz(MX) {data.pb(Node()); };
void extend(int v) {
if(data[v].lc == -1) {
data[v].lc = nxt++;
data.pb(Node());
}
if(data[v].rc == -1) {
data[v].rc = nxt++;
data.pb(Node());
}
}
void update(int tl, int tr, int v, int ind, int val) {
if(tl == tr) {
data[v].sz++; data[v].sum += tl;
return;
}
int tm = (tl + tr) >> 1;
extend(v);
if(ind <= tm) {
update(tl, tm, data[v].lc, ind, val);
}
else {
update(tm + 1, tr, data[v].rc, ind, val);
}
data[v].sum = data[data[v].lc].sum + data[data[v].rc].sum;
data[v].sz = data[data[v].lc].sz + data[data[v].rc].sz;
}
void insert(int val) {
// if(!(0ll < val && val < MX)) {
// return;
// }
update(0, sz, 0, val, 1);
}
lli query(int tl, int tr, int v, int els, int add = 0) {
if(tl == tr) {
if(add + data[v].sz < els) return INF;
return (1ll * els - add) * tl;
}
int tm = (tl + tr) >> 1;
extend(v);
if(els <= add + data[data[v].lc].sz) {
return 1ll * query(tl, tm, data[v].lc, els, add);
}
else {
return 1ll * data[data[v].lc].sum + query(tm + 1, tr, data[v].rc, els, add + data[data[v].lc].sz);
}
}
lli k_sum(int sm) {
return min(INF, query(0ll, sz, 0, sm));
}
};
vector<SegT> st;
void prec(int node, int par, int cst) {
p[node] = array<int, 2>({par, cst});
tin[node] = timer++;
roots.insert({tin[node], node});
for(auto itr = adj[node].begin(); itr != adj[node].end(); ) {
int c = (*itr)[0];
if(c == par) {
itr = adj[node].erase(itr);
continue;
}
prec((int)c, node, (*itr)[1]);
itr++;
}
}
array<lli, 2> dfs(int node) {
vis[node] = k;
// cout<<"dfs : " << node << endl;
int csz = 0;
vector<lli> A1, A2;
vector<int> srt;
array<lli,2> ret = {INF, INF};
lli sum = 0;
for(auto &c : adj[node]) {
if(deg[c[0]] <= k) {
break;
}
srt.pb(csz);
csz++;
auto tmp = dfs((int)c[0]);
A1.pb(tmp[1] + c[1]); A2.pb(tmp[0]);
sum += min(tmp[0], tmp[1] + c[1]);
}
auto comp = [&](const int &x, const int &y) {
// assert(max(x, y) < min(A1.size(), A2.size()));
return A1[x] - A2[x] < A1[y] - A2[y];
};
int cnt = deg[node] - k;
// assert(cnt > 0);
sort(all(srt), comp);
vector<lli> cev(csz + 1);
cev[0] = sum;
for(int i = 1; i <= csz; i++) {
cev[i] = cev[i - 1] - min(A1[srt[i - 1] ], A2[srt[i - 1]]) + A1[srt[i - 1]];
}
for(int i = 0; i <= min(cnt, csz); i++) {
ret[0] = min(ret[0], cev[i] + st[node].k_sum(cnt - i));
if(i < cnt) ret[1] = min(ret[1], cev[i] + st[node].k_sum(cnt - i - 1));
}
// cout << "node:"<<node<<" normal:"<<ret[0]<<" del par:"<<ret[1]<<"\n";
// cout<<"cnt:"<<cnt<<"csz:"<<csz<<"\n";
return ret;
}
lli solve_k() {
// cout<<"k:"<<k<<"\n\n";
while(deg_nodes.size() && deg_nodes.back()[0] == k) {
auto cur = deg_nodes.back();
// cout<<"erase:"<<cur[1]<<"\n";
roots.erase({tin[cur[1]], cur[1]});
st[p[cur[1]][0]].insert(p[cur[1]][1]);
for(auto &c : adj[cur[1]]) {
st[c[0]].insert(c[1]);
}
deg_nodes.pop_back();
}
lli ret = 0;
for(auto &c : roots) {
if(vis[c[1]] == k) continue;
ret += dfs(c[1])[0];
}
return ret;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n = N;
lli sum = 0ll;
for(int i = 0; i<n - 1; i++) {
V[i]++; U[i]++;
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
sum += W[i];
}
vector<lli> ans(n);
deg_nodes.resize(n);
for(int i = 1; i<=n; i++) {
deg[i] = (int)adj[i].size();
deg_nodes[i - 1] = {deg[i], i};
}
sort(rall(deg_nodes));
auto comp = [](const array<int,2> &x, const array<int,2> &y) { return deg[x[0]] < deg[y[0]]; };
for(int i = 1; i<=n; i++) {
sort(rall(adj[i]), comp);
}
prec(1, 0, 0);
ans[0] = sum;
st.assign(n + 3, SegT());
for(int i = 1; i<=n - 1; i++) {
// cout<<"i:"<<i<<endl;
k = i;
ans[i] = solve_k();
}
return ans;
}
