#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
const int NN = 1e5+3;
const ll INF = 1e16;
vector<int> inp[NN], Vdeg[NN], grf[NN];
int pre[NN], cnt;
bool odw[NN];
ll Dp[NN][2], C[NN];
// dla n^2 log
vector<ll> tmpX, tmpY;
bool comp(int a, int b){
return (int)inp[a].size() > (int)inp[b].size();
}
void set_pre(int v, int p){
pre[v]=cnt; cnt++;
for(auto w:inp[v]){
if(w==p) continue;
set_pre(w, v);
}
}
int get_x(int v, int k){
int out=0;
for(auto w:inp[v]) if((int)inp[w].size()<=k && pre[v]<pre[w]) out++, tmpX.pb(C[w]);
sort(tmpX.begin(), tmpX.end());
return out;
}
ll get_y(int v, int k){
ll out = 0;
for(auto w:inp[v]) if((int)inp[w].size()>k && pre[v]<pre[w]) out+=Dp[w][0], tmpY.pb(Dp[w][1]-Dp[w][0]);
sort(tmpY.begin(), tmpY.end());
return out;
}
ll get_sm_x(int x){
ll out=0;
for(int i=0; i<x; i++) out += tmpX[i];
return out;
}
ll get_sm_y(int x){
ll out=0;
for(int i=0; i<x; i++) out += tmpY[i];
return out;
}
void get_out(int v, int k){
odw[v]=1;
for(auto w:grf[v]){
if(odw[w]) continue;
get_out(w, k);
}
tmpX.clear(); tmpY.clear();
int diff = (int)inp[v].size()-k;
int X = get_x(v, k);
ll smY = get_y(v, k);
int Y = (int)tmpY.size();
for(int i=diff; i>=0; i--){
if(i<=X && diff-i<=Y) Dp[v][0]=min(Dp[v][0], get_sm_x(i)+smY+get_sm_y(diff-i));
if(0<= i-1 && i-1<=X && diff-i<=Y) Dp[v][1]=min(Dp[v][1], get_sm_x(i-1)+smY+get_sm_y(diff-i)+C[v]);
if(0<= i-1 && i<=X && diff-i+1<=Y) Dp[v][1]=min(Dp[v][1], get_sm_x(i)+smY+get_sm_y(diff-i+1)+C[v]);
}
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
//PREPROCES
int n=N;
for(int i=0; i<n-1; i++){
inp[U[i]].pb(V[i]);
inp[V[i]].pb(U[i]);
}
for(int i=0; i<n; i++) Dp[i][0]=Dp[i][1]=INF;
for(int i=0; i<n; i++) Vdeg[(int)inp[i].size()].pb(i);
set_pre(0, 0);
for(int i=0; i<n-1; i++){
if(pre[U[i]]<pre[V[i]]) C[V[i]] = W[i];
else C[U[i]] = W[i];
}
C[0] = INF;
for(int i=0; i<n; i++) sort(inp[i].begin(), inp[i].end(), comp);
//WYNIK
vector<pair<int, int>> Vert;
vector<ll> WYNIK;
for(int k=n-1; k>=0; k--){
ll out=0;
for(auto v:Vdeg[k+1]){
Vert.pb({pre[v], v});
for(auto w:inp[v]){
if(inp[w].size()>=k+1) grf[v].pb(w);
if(inp[w].size()>k+1) grf[w].pb(v);
}
}
sort(Vert.begin(), Vert.end());
for(auto Ve:Vert){
int v=Ve.nd;
if(odw[v]) continue;
get_out(v, k);
out+=min(Dp[v][0], Dp[v][1]);
}
WYNIK.pb(out);
//CZYSZCZENIE
for(auto v:Vert){
odw[v.nd]=0;
Dp[v.nd][0]=Dp[v.nd][1]=INF;
}
}
reverse(WYNIK.begin(), WYNIK.end());
return WYNIK;
}
