#include "roads.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, k;
vector<vector<pair<int, int>>> tree;
vector<int> p;
vector<ll> pe;
vector<int> deg;
vector<int> depth;
vector<ll> dp[2];
vector<vector<int>> forest;
vector<bool> visited;
vector<multiset<ll>> ms;
void pre_dfs(int nd, int ss, int d = 0){
depth[nd] = d;
for(auto [x, w]: tree[nd]) if(x != ss){
pre_dfs(x, nd, d+1);
p[x] = nd;
pe[x] = w;
ms[nd].insert(w);
}
}
void dfs(int nd){
visited[nd] = 1;
ll sum = 0;
for(int x: forest[nd]){
dfs(x);
sum+=dp[1][x];
ms[nd].insert(-dp[1][x]+min(dp[0][x], dp[1][x])+pe[x]);
}
dp[0][nd] = sum, dp[1][nd] = sum;
int c = ms[nd].size();
if(c-k > 0){
auto it = ms[nd].begin();
for(int i = 0; i < c-k; i++) dp[0][nd]+=*it, it++;
}
if(c-k+1 > 0){
auto it = ms[nd].begin();
for(int i = 0; i < c-k+1; i++) dp[1][nd]+=*it, it++;
}
for(int x: forest[nd]){
ms[nd].erase(ms[nd].find(-dp[1][x]+min(dp[0][x], dp[1][x])+pe[x]));
}
}
vector<ll> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W){
swap(n, _n);
tree.resize(n);
p.assign(n, -1);
pe.resize(n);
deg.assign(n, 0);
depth.resize(n);
fill(dp, dp+2, vector<ll>(n, 0));
forest.resize(n);
visited.assign(n, 0);
ms.resize(n);
for(int i = 0; i < n-1; i++){
deg[U[i]]++, deg[V[i]]++;
tree[U[i]].pb({V[i], W[i]});
tree[V[i]].pb({U[i], W[i]});
}
pre_dfs(0, -1);
vector<int> o(n);
for(int i = 0; i < n; i++) o[i] = i;
sort(o.begin(), o.end(), [&](int a, int b){
return deg[a] > deg[b];
});
vector<ll> ans(n, 0);
for(int w: W) ans[0]+=w;
for(k = n-1; k > 0; k--){
vector<int> nodes;
for(int i = 0; i < n; i++){
if(deg[o[i]] <= k) break;
nodes.pb(o[i]);
if(deg[p[o[i]]] > k){
forest[p[o[i]]].pb(o[i]);
ms[p[o[i]]].erase(ms[p[o[i]]].find(pe[o[i]]));
}
}
sort(nodes.begin(), nodes.end(), [&](int a, int b){
return depth[a] < depth[b];
});
for(int nd: nodes) if(!visited[nd]) dfs(nd), ans[k]+=dp[0][nd];
for(int nd: nodes){
forest[nd].clear();
visited[nd] = 0;
if(deg[p[nd]] > k){
ms[p[nd]].insert(pe[nd]);
}
}
}
return ans;
}
