#include "roads.h"
//#include "grader_road.cpp"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define orderset tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>
const int MAXN=1e5;
ll DP[MAXN][2];
int vis[MAXN];
vector<set<pair<int,int>>> graph(MAXN);
vector<orderset> se(MAXN);
struct fenwick{
vector<ll> bit;
map<pair<int,int>,int> mp;
void setup(vector<pair<int,int>> &v){
for(int i=0;i<v.size();i++){
mp[v[i]]=1;
}
int tim=1;
for(pair<const pair<int,int>,int> &x:mp){
x.second=tim;
tim++;
}
bit.assign(tim,0);
}
void update(pair<int,int> &pos,int x){
assert(mp.find(pos)!=mp.end());
int i=mp[pos];
for(;i<bit.size();i+=(i&(-i))){
bit[i]+=x;
}
}
ll query(pair<int,int> &pos){
int i=mp[pos];
ll curr=0;
for(;i;i-=(i&(-i))){
curr+=bit[i];
}
return curr;
}
};
fenwick bit[MAXN];
void DFS(int u,int p,int req){
vis[u]=req;
const ll limit=1e18;
DP[u][0]=limit,DP[u][1]=limit;
ll curr=0;
vector<ll> diff;
int counter=se[u].size();
for(auto it=graph[u].begin();it!=graph[u].end();it++){
int v=(*it).first,w=(*it).second;
if(v!=p){
DFS(v,u,req);
if(DP[v][1]+w<=DP[v][0]){
curr+=(DP[v][1]+w);
}
else{
curr+=DP[v][0];
counter++;
diff.push_back(DP[v][1]+w-DP[v][0]);
}
}
}
diff.push_back(0);
sort(diff.begin(),diff.end());
for(int i=0;i<diff.size();i++){
curr+=diff[i];
if(counter-i<=req){
DP[u][1]=min(DP[u][1],curr);
}
else if(counter-i-(int)se[u].size()<=req){
pair<int,int> x=(*se[u].find_by_order(counter-i-req-1));
DP[u][1]=min(DP[u][1],curr+bit[u].query(x));
}
if(counter-i<=req-1){
DP[u][0]=min(DP[u][0],curr);
}
else if(counter-i-(int)se[u].size()<=req-1){
pair<int,int> x=(*se[u].find_by_order(counter-i-req));
DP[u][0]=min(DP[u][0],curr+bit[u].query(x));
}
}
}
vector<long long> minimum_closure_costs(int n,vector<int> u,vector<int> v,vector<int> w){
vector<ll> ans;
ans.assign(n,0);
int deg[n]={0};
for(int i=0;i<n-1;i++){
ans[0]+=w[i];
deg[u[i]]++,deg[v[i]]++;
graph[u[i]].insert({v[i],w[i]});
graph[v[i]].insert({u[i],w[i]});
}
for(int u=0;u<n;u++){
vector<pair<int,int>> temp;
for(auto it=graph[u].begin();it!=graph[u].end();it++){
int v=(*it).first,w=(*it).second;
temp.push_back({w,v});
}
bit[u].setup(temp);
}
vector<pair<int,int>> order(n);
for(int i=0;i<n;i++){
order[i]={deg[i],i};
}
sort(order.begin(),order.end());
int ptr=0;
for(int d=1;d<=n;d++){
//cout << "HERE " << d << endl;
while(ptr<order.size()&&order[ptr].first<=d){
int u=order[ptr].second;
ptr++;
for(auto it=graph[u].begin();it!=graph[u].end();it++){
int v=(*it).first,w=(*it).second;
graph[v].erase({u,w});
pair<int,int> bruh={w,u};
se[v].insert(bruh);
bit[v].update(bruh,w);
}
graph[u].clear();
}
for(int i=ptr;i<n;i++){
if(vis[order[i].second]!=d){
DFS(order[i].second,-1,d);
ans[d]+=DP[order[i].second][1];
}
}
}
return ans;
}
