#include "roads.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<pair<int, int>>> G(100000);
vector<vector<int>> H(100000);
int w[100000], par[100000], dep[100000];
void dfs_build(int v, int p = -1, int depth = 0){
dep[v] = depth;
for(auto i : G[v]){
if(i.first != p){
dfs_build(i.first, v, depth + 1);
w[i.first] = i.second;
par[i.first] = v;
}
}
}
int dp[100000][2];
int n;
vector<long long> had;
bool isHeavy[100000];
vector<pair<int, int>> deg;
// vector<vector<int>> store(100001);
bool visited[100000];
int d(int v, int u){
if(v == -1 || u == -1) return (1LL << 60);
return (dep[v] > dep[u]) ? w[v] : w[u];
}
struct item {
int key, prior, cnt = 0, sum = 0;
item * l, * r;
item() { }
item (int key, int prior) : key(key), prior(prior), cnt(1), sum(key), l(nullptr), r(nullptr) { }
};
typedef item * pitem;
int cnt (pitem t) {
return t ? t->cnt : 0;
}
int sum (pitem t){
return t ? t->sum : 0;
}
void upd_cnt (pitem t) {
if (t) t->cnt = 1 + cnt(t->l) + cnt(t->r);
}
void upd_sum (pitem t) {
if (t) t->sum = t->key + sum(t->l) + sum(t->r);
}
void split (pitem t, int key, pitem & l, pitem & r) {
if (!t)
l = r = NULL;
else if (key < t->key)
split (t->l, key, l, t->l), r = t;
else
split (t->r, key, t->r, r), l = t;
upd_cnt(t);
upd_sum(t);
}
void insert (pitem & t, pitem it) {
if (!t)
t = it;
else if (it->prior > t->prior)
split (t, it->key, it->l, it->r), t = it;
else
insert (it->key < t->key ? t->l : t->r, it);
upd_cnt(t);
upd_sum(t);
}
void merge (pitem & t, pitem l, pitem r) {
if (!l || !r)
t = l ? l : r;
else if (l->prior > r->prior)
merge (l->r, l->r, r), t = l;
else
merge (r->l, l, r->l), t = r;
upd_cnt(t);
upd_sum(t);
}
void erase (pitem & t, int key) {
if (t->key == key) {
pitem th = t;
merge (t, t->l, t->r);
delete th;
}
else
erase (key < t->key ? t->l : t->r, key);
upd_cnt(t);
upd_sum(t);
}
pitem unite (pitem l, pitem r) {
if (!l || !r) return l ? l : r;
if (l->prior < r->prior) swap (l, r);
pitem lt, rt;
split (r, l->key, lt, rt);
l->l = unite (l->l, lt);
l->r = unite (l->r, rt);
return l;
}
int query(pitem & t, int k){
if(!t || k == 0) return 0;
if(cnt(t) == k) return t->sum;
int res = 0;
if(k <= cnt(t->l)) return query(t->l, k);
if(cnt(t->l) + 1 <= k){
res += sum(t->l);
res += t->key;
res += query(t->r, k - (cnt(t->l) + 1));
}
return res;
}
pitem store[100001];
void dfs(int v, int p = -1, int k = -1){
visited[v] = true;
vector<int> val;
int ans = 0;
int cnt = 0;
for(auto i : H[v]){
if(i != p){
dfs(i, v, k);
if(dp[i][0] <= dp[i][1]){
ans += dp[i][0];
cnt++;
continue;
}else{
ans += dp[i][1];
val.push_back(dp[i][0] - dp[i][1]);
}
}
}
for(auto i : val){
pitem pi = new item(i, rng());
insert(store[v], pi);
}
{
int res = ans, to_del = max(0LL, (int) (G[v].size() - 1) - (k - 1) - cnt + 1);
res += query(store[v], to_del);
dp[v][1] = res;
}
{
int res = ans + d(v, p), to_del = max(0LL, (int) (G[v].size() - 1) - (k) - cnt + 1);
res += query(store[v], to_del);
dp[v][0] = res;
}
for(auto i : val){
erase(store[v], i);
}
}
void migrate(int u, int v){ // u to v
int weight = (dep[u] > dep[v] ? w[u] : w[v]);
pitem pi = new item(weight, rng());
insert(store[u], pi);
}
set<pair<int, int>> E;
void del_e(int u, int v){
if(u > v) swap(u, v);
E.erase({u, v});
}
void del(int v){
for(auto i : G[v]){
if(isHeavy[i.first]){
migrate(i.first, v);
del_e(i.first, v);
}
}
}
vector<long long> minimum_closure_costs(int32_t N, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
for(int i = 0; i < N; i++){
store[i] = new item(0, rng());
}
n = N;
had.resize(N);
for(int i = 0; i < N - 1; i++){
if(U[i] > V[i]) swap(U[i], V[i]);
G[U[i]].push_back({V[i], W[i]});
G[V[i]].push_back({U[i], W[i]});
E.insert({U[i], V[i]});
}
for(int i = 0; i < N; i++){
deg.push_back({G[i].size(), i});
}
sort(deg.begin(), deg.end());
int idx = 0;
dfs_build(0);
w[0] = (1LL << 60);
fill(isHeavy, isHeavy + N, 1);
for(int k = 0; k < N; k++){
while(idx < N && deg[idx].first <= k){
del(deg[idx].second);
isHeavy[deg[idx].second] = false;
idx++;
}
for(int i = idx; i < N; i++) visited[deg[i].second] = false;
for(int i = idx; i < N; i++){
H[deg[i].second].clear();
}
for(auto i : E){
H[i.first].push_back(i.second);
H[i.second].push_back(i.first);
}
for(int i = idx; i < N; i++){
int v = deg[i].second;
if(!visited[v]){
dfs(v, -1, k);
had[k] += min(dp[v][0], dp[v][1]);
}
}
// cout << "FOR " << k << ": " << endl;
// for(int i = 0; i < n; i++){
// cout << dp[i][0] << ' ' << dp[i][1] << endl;
// }
}
return had;
}
