#include<bits/stdc++.h>
#include "roads.h"
#define MAXN 100007
using namespace std;
const long long inf=1e10;
int n,a,b,k;
long long sum;
vector< pair<int,int> > v[MAXN];
long long dp[MAXN][2];
int li[MAXN][2],tim;
long long ff(int x,int p,bool par){
if(li[x][par]==tim)return dp[x][par];
li[x][par]=tim;
dp[x][par]=0;
vector<long long> s;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p){
if(par)dp[x][par]+=v[x][i].second;
continue;
}
s.push_back(ff(v[x][i].first,x,true)-ff(v[x][i].first,x,false));
dp[x][par]+=ff(v[x][i].first,x,false);
}
sort(s.begin(),s.end());
if(int(v[x].size())-k-par>int(s.size()))cout<<1/0;
for(int i=0;i<int(v[x].size())-k-par;i++){
dp[x][par]+=s[i];
}
return dp[x][par];
}
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
n=N;
for(int i=1;i<=n-1;i++){
a=U[i-1]; b=V[i-1];
a++; b++;
v[a].push_back({b,W[i-1]});
v[b].push_back({a,W[i-1]});
sum+=W[i-1];
}
vector<long long> res={sum};
for(int i=1;i<=n-1;i++){
k=i; tim++;
res.push_back(ff(1,0,0));
}
return res;
}
/*int main(){
//vector<long long> s=minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});
vector<long long> s=minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
for(long long i:s)cout<<i<<" ";
return 0;
}*/
