#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
const ld PI = 3.1415926535;
const int N = 5e5+10;
const int M = 1e4 + 5;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;
ll dp[N][2], sm[N], used[N];
int n, k, tresh = 165;
vector<pair<ll, ll>> g[N];
vector<pair<ll, ll>> ng[N];
vector<ll> vs[N];
pair<ll, pll> tmp[N];
void dfs(int v, int p, int w){
dp[v][0] = dp[v][1] = 0;
for(auto u : g[v])
if(u.F != p)
dfs(u.F, v, u.S);
int ctmp = 0;
for(auto u : g[v]){
if(u.F != p){
tmp[ctmp++] = {dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}};
}
}
sort(tmp, tmp + ctmp);
reverse(tmp, tmp + ctmp);
for(int i = 0; i < min(k, ctmp); i++){
if(tmp[i].F > 0){
dp[v][0] += tmp[i].S.F;
}else{
dp[v][0] += tmp[i].S.S;
}
}
for(int i = min(k, ctmp); i < ctmp; i++){
dp[v][0] += tmp[i].S.S;
}
for(int i = 0; i < min(k - 1,ctmp); i++){
if(tmp[i].F > 0){
dp[v][1] += tmp[i].S.F;
}else{
dp[v][1] += tmp[i].S.S;
}
}
for(int i = min(k - 1, ctmp); i < ctmp; i++){
dp[v][1] += tmp[i].S.S;
}
dp[v][1] += w;
}
void dfs1(int v, int p, int w){
used[v] = 1;
dp[v][0] = dp[v][1] = 0;
for(auto u : ng[v]){
if(u.F != p)
dfs1(u.F, v, u.S);
}
//cout << v << '\n';
while(sz(vs[v]) > k){
sm[v] -= vs[v].back();
vs[v].pop_back();
}
int ps = min(sz(vs[v]), k) - 1, cur = min(sz(vs[v]), k);
vector<pair<ll, pll>> ha = {};
for(auto u : ng[v]){
if(u.F != p){
ha.pb({dp[u.F][1] - dp[u.F][0], {dp[u.F][1], dp[u.F][0]}});
}
}
/*cout << sm[v] << ": ";
for(auto e : vs[v]){
cout << e << ' ';
}
cout << '\n';*/
sort(all(ha));
reverse(all(ha));
dp[v][0] = sm[v];
for(auto e : ha){
//cout << e.F << ' ' << e.S.F << ' ' << e.S.S << ' ' << ps << ' ' << cur << '\n';
if(e.F <= 0 || ps < 0){
dp[v][0] += e.S.S;
//cout << "1\n";
}else{
if(cur < k){
cur++;
dp[v][0] += e.S.F;
//cout << "2\n";
}else{
if(e.F > vs[v][ps]){
dp[v][0] -= vs[v][ps];
dp[v][0] += e.S.F;
ps--;
//cout << "3\n";
}else{
dp[v][0] += e.S.S;
//cout << "4\n";
}
}
}
}
while(sz(vs[v]) > k - 1){
sm[v] -= vs[v].back();
vs[v].pop_back();
}
/*cout << sm[v] << ": ";
for(auto e : vs[v]){
cout << e << ' ';
}
cout << '\n';*/
ps = min(sz(vs[v]), k - 1) - 1, cur = min(sz(vs[v]), k - 1);
dp[v][1] = sm[v] + w;
for(auto e : ha){
if(e.F <= 0 || ps < 0){
dp[v][1] += e.S.S;
}else{
if(cur < k - 1){
cur++;
dp[v][1] += e.S.F;
}else{
if(e.F > vs[v][ps]){
dp[v][1] -= vs[v][ps];
dp[v][1] += e.S.F;
ps--;
}else{
dp[v][1] += e.S.S;
}
}
}
}
//cout << dp[v][0] << ' ' << dp[v][1] << '\n';
}
vector<long long> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W) {
n = _n;
vector<ll> ans(n, 0);
for(int i = 0; i < n - 1; i++){
U[i]++;
V[i]++;
g[V[i]].pb({U[i], W[i]});
g[U[i]].pb({V[i], W[i]});
ans[0] += W[i];
}
k = 1;
for(; k < min(tresh, n); k++){
dfs(1, -1, 0);
ans[k] = ans[0] - dp[1][0];
}
vector<int> heavy = {};
ll ad = 0;
for(int i = 1; i <= n; i++){
if(sz(g[i]) > tresh){
heavy.pb(i);
for(auto e : g[i]){
int u = e.F, w = e.S;
if(sz(g[u]) > tresh){
ng[i].pb({u, w});
}else{
vs[i].pb(w);
}
}
sort(all(vs[i]));
reverse(all(vs[i]));
for(auto e : vs[i])
sm[i] += e;
}else{
for(auto e : g[i]){
int u = e.F, w = e.S;
if(sz(g[u]) <= tresh){
ad += w;
}
}
}
}
ad /= 2;
/*for(auto e : heavy){
cout << e << ' ' << sm[e] << ": ";
for(auto u : ng[e]){
cout << "(" << u.F << ", " << u.S << ") ";
}
for(auto u : vs[e]){
cout << u << ' ';
}
cout << '\n';
}
cout << ad << "\n";*/
for(k = n - 1; k >= tresh; k--){
//cout << k << ":\n";
ll ret = ad;
for(auto e : heavy){
if(!used[e]){
dfs1(e, -1, 0);
ret += dp[e][0];
}
}
for(auto e : heavy)
used[e] = 0;
ans[k] = ans[0] - ret;
}
return ans;
}
