#include <iostream>
#include <vector>
#include <algorithm>
#include "roads.h"
using namespace std;
#define ll long long
const int N = 1e5 + 10;
vector<pair<int,int>> ch[N];
ll Mn[N];
ll dp[N][2];
vector<ll> sub1(int n,vector<int> W){
sort(rbegin(W),rend(W));
vector<ll> v;
v.push_back(0);
for (int i : W)
v[0] += i;
for (int i : W)
v.push_back(v.back() - i);
return v;
}
vector<ll> sub2(int n,vector<int> W){
ll t = W[0];
ll nt = 0;
vector<ll> v(n,0);
v[0] += W[0];
for (int i=1;i<n-1;i++){
ll a = t;
t = min(t,nt) + W[i];
nt = a;
v[0] += W[i];
}
v[1] = min(t,nt);
return v;
}
void dfs(int u,int k,int p = -1,ll W = 1e12){
int d = ch[u].size();
vector<ll> Mn(d + 5,1e17);
Mn[0] = 0;
for (auto [i,w] : ch[u]){
if (i == p)
continue;
dfs(i,k,u,w);
for (int j=d;j>=0;j--){
Mn[j + 1] = min(Mn[j + 1],Mn[j] + dp[i][1]);
Mn[j + 1] = min(Mn[j + 1],Mn[j] + dp[i][0] + w);
Mn[j] += dp[i][0];
}
}
int to_rem = max(0,d - k);
dp[u][0] = Mn[to_rem];
dp[u][1] = (to_rem != 0 ? Mn[to_rem - 1] : 0) + W;
}
vector<ll> sub3(int n,vector<int> U,vector<int> V,vector<int> W){
for (int i=0;i<n-1;i++){
ch[U[i] + 1].push_back({V[i] + 1,W[i]});
ch[V[i] + 1].push_back({U[i] + 1,W[i]});
}
vector<ll> v;
for (int k=0;k<n;k++){
for (int i=0;i<=n;i++)
for (int j : {0,1})
dp[i][j] = 1e17;
dfs(1,k);
v.push_back(dp[1][0]);
}
return v;
}
vector<ll> minimum_closure_costs(int n,vector<int> U,vector<int> V,vector<int> W){
if (n <= 2000)
return sub3(n,U,V,W);
long long sum = 0,sum2 = 0,sum3 = 0;
for (int i=0;i<n-1;i++)
sum += U[i],sum2 += W[i],sum3 += (U[i] == i);
if (sum == 0)
return sub1(n,W);
// if (sum2 == n-1)
// return sub5(n,U,V);
if (sum3 == n-1)
return sub2(n,W);
}
