#include "roads.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<pair<ll,int>,null_type,less<pair<ll,int> >,rb_tree_tag,tree_order_statistics_node_update> oset;
const int MAXN = 1e5 + 16;
const int INF = 1e9 + 16;
const ll INFLL = 1e16 + 16;
oset dpCost[MAXN];
vector<pair<int,ll> > adj[MAXN];
int ptrDp[MAXN],dep[MAXN],idxPar[MAXN];
ll costPar[MAXN],currBack[MAXN],currCost = 0;
void change(pair<ll,int> u,pair<ll,int> v,int id,int mn){
if(u < *(dpCost[id].find_by_order(ptrDp[id]))){
ptrDp[id]--;
currCost -= u.first;
}
dpCost[id].erase(u);
if(v < *(dpCost[id].find_by_order(ptrDp[id]))){
ptrDp[id]++;
currCost += v.first;
}
dpCost[id].insert(v);
while(ptrDp[id] < max(0,mn)){
currCost += dpCost[id].find_by_order(ptrDp[id]++)->first;
}
while(ptrDp[id] > max(0,mn) && dpCost[id].find_by_order(ptrDp[id]-1)->first > 0){
currCost -= dpCost[id].find_by_order(--ptrDp[id])->first;
}
while(dpCost[id].find_by_order(ptrDp[id])->first < 0){
currCost += dpCost[id].find_by_order(ptrDp[id]++)->first;
}
}
void dfs(int u,int p){
for(auto v : adj[u]){
if(v.first != p){
dep[v.first] = dep[u] + 1;
dpCost[u].insert(make_pair(v.second,v.first));
currBack[v.first] = v.second;
ptrDp[u]++;
dfs(v.first,u);
}else{
costPar[u] = v.second;
idxPar[u] = v.first;
}
}
}
vector<ll> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
for(int i=0;i<N-1;i++){
adj[U[i]].emplace_back(V[i],W[i]);
adj[V[i]].emplace_back(U[i],W[i]);
currCost += W[i];
}
adj[N].emplace_back(0,0);
adj[0].emplace_back(N,0);
for(int i=0;i<=N;i++){
dpCost[i].insert(make_pair(INFLL,INF));
}
dfs(N,N);
priority_queue<pair<int,int> > pq;
for(int i=0;i<N;i++){
pq.emplace(dep[i],i);
}
vector<ll> res;
res.emplace_back(currCost);
for(int i=1;i<N;i++){
vector<pair<int,int> > proceed;
while(!pq.empty()){
auto curr = pq.top();
int id = curr.second;
pq.pop();
if(adj[id].size() < i){
continue;
}
proceed.emplace_back(curr);
change(make_pair(INFLL,INF),make_pair(INFLL,INF),id,(int)adj[id].size()-i-1);
ll temp = currCost + costPar[id];
change(make_pair(INFLL,INF),make_pair(INFLL,INF),id,(int)adj[id].size()-i);
temp -= currCost;
change(make_pair(currBack[id],id),make_pair(temp,id),idxPar[id],(int)adj[idxPar[id]].size()-i);
currBack[id] = temp;
}
res.emplace_back(currCost);
for(auto u : proceed){
pq.emplace(u);
}
}
return res;
}
