#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) int32_t(x.size())
#define int long long
const int maxn = 2e3+10;
const int inf = 1e18+10;
const int mnv = -1e15-10;
const int mxv = 1e15+10;
int n, dp[maxn][2];
vector<int> g[maxn];
vector<pair<int,int>> gesp[maxn];
int cnt[maxn];
vector<int> trq[maxn], trs[maxn], f1[maxn], f2[maxn];
//add/remove pos from id
int att(int no, int l, int r, int id, int pos, int val) {
if(l > pos || r < pos) return no;
if(no == 0) {
no = ++cnt[id];
}
//trq[id][trq[id].size()-1]
while(no > sz(trq[id])-1) {
trq[id].pb(0);
trs[id].pb(0);
f1[id].pb(0);
f2[id].pb(0);
}
// cout << " " << no << " " << l << " " << r << " " << pos << " " << val << endl;
if(l == r) {
trq[id][no]+= val;
trs[id][no]+= val*pos;
return no;
}
int mid = (l+r)>>1;
f1[id][no] = att(f1[id][no],l,mid,id,pos,val);
f2[id][no] = att(f2[id][no],mid+1,r,id,pos,val);
trq[id][no] = trq[id][f1[id][no]]+trq[id][f2[id][no]];
trs[id][no] = trs[id][f1[id][no]]+trs[id][f2[id][no]];
return no;
}
int find(int no, int l, int r, int id, int val) {
// cout << no << " " << l << " " << r << " " << trq[id][no] << " " << trs[id][no] << " " << val << endl;
//quero pegar os val menores caras em (l,r)
if(no == 0) return 0;
if(l == r) {
// cout << l << " " << val << endl;
return val*r;
}
int mid = (l+r)>>1;
if(trq[id][f1[id][no]] >= val) return find(f1[id][no],l,mid,id,val);
else return trs[id][f1[id][no]]+find(f2[id][no],mid+1,r,id,val-trq[id][f1[id][no]]);
}
void dfs(int u, int qtd, int ant) {
// mark[u] = qtd+1;
int ans = 0;
vector<int> use;
for(auto V : gesp[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
dfs(v,qtd,u);
ans+= min(dp[v][0],dp[v][1]+w);
use.pb(-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w);
att(1,mnv,mxv,u,-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w,1);
}
//se nao tem a aresta com o pai -> sz(g[u])-1-qtd = t
dp[u][0] = dp[u][1] = inf;
if(sz(g[u])-qtd-1 <= 0) dp[u][1] = ans;
else dp[u][1] = ans+find(1,mnv,mxv,u,sz(gesp[u])-qtd-1);
if(sz(g[u])-qtd <= 0) dp[u][0] = ans;
else dp[u][0] = ans+find(1,mnv,mxv,u,sz(gesp[u])-qtd);
// for(int i = 1; i <= sz(g[u])-qtd; i++) {
// ans+= use[i-1];
// if(i == sz(g[u])-qtd-1) dp[u][1] = ans;
// if(i == sz(g[u])-qtd) dp[u][0] = ans;
// }
}
std::vector<int> minimum_closure_costs(int32_t N, std::vector<int32_t> U,std::vector<int32_t> V,std::vector<int32_t> W) {
n = N;
vector<int> ans;
int sumw = 0;
for(int i = 0; i < n-1; i++) {
int u = U[i];
int v = V[i];
int w = W[i];
sumw+= w;
g[u].pb(i);
g[v].pb(i);
gesp[u].pb(mp(v,w));
gesp[v].pb(mp(u,w));
}
ans.pb(sumw);
for(int k = 1; k <= n-1; k++) {
for(int i = 0; i < n; i++) {
cnt[i] = 1;
trq[i].clear(); trq[i].resize(60*sz(gesp[i])+5,0);
trs[i].clear(); trs[i].resize(60*sz(gesp[i])+5,0);
f1[i].clear(); f1[i].resize(60*sz(gesp[i])+5,0);
f2[i].clear(); f2[i].resize(60*sz(gesp[i])+5,0);
}
dfs(0,k,-1);
ans.pb(dp[0][0]);
}
return ans;
}
