#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
const int maxn=100000+10;
struct yal{
int u,v,w;
int getad(int fu){
int ret=(u^v^fu);
return ret;
}
};
long long sum=0;
yal alled[maxn];
vector<int>adj[maxn],fake[maxn];
set<int>allrishe;
int n,vis[maxn],len[maxn],par[maxn];
long long dp0[maxn],dp1[maxn],fdp0[maxn],fdp1[maxn];
set<pair<long long,int>>st[maxn],sta[maxn];
set<pair<int,int>>sortlen;
void aval(int u,int lena,int para=-1){
par[u]=para;
len[u]=lena;
for(auto xx:adj[u]){
int x=alled[xx].getad(u);
if(xx!=para){
fake[u].push_back(xx);
aval(x,lena+1,xx);
}
}
}
void del(int u,int i){
vis[u]=1;
sortlen.erase(make_pair(-len[u],u));
allrishe.erase(u);
if(u!=0){
if(st[alled[par[u]].getad(u)].count(make_pair(fdp1[u]-fdp0[u],u))!=0){
dp0[alled[par[u]].getad(u)]-=fdp1[u]-fdp0[u];
st[alled[par[u]].getad(u)].erase(make_pair(fdp1[u]-fdp0[u],u));
}
else{
sta[alled[par[u]].getad(u)].erase(make_pair(fdp1[u]-fdp0[u],u));
}
dp0[alled[par[u]].getad(u)]-=fdp0[u];
sta[alled[par[u]].getad(u)].insert(make_pair(alled[par[u]].w,u));
}
for(auto xx:fake[u]){
int x=alled[xx].getad(u);
if(vis[x]==0){
allrishe.insert(x);
}
}
for(auto xx:adj[u]){
int x=alled[xx].getad(u);
if(vis[x]==1){
sum-=alled[xx].w;
}
}
}
void upd(int u,int i){
if(u!=0){
dp0[alled[par[u]].getad(u)]-=fdp0[u];
long long z=fdp1[u]-fdp0[u];
if(st[alled[par[u]].getad(u)].count(make_pair(z,u))!=0){
dp0[alled[par[u]].getad(u)]-=z;
st[alled[par[u]].getad(u)].erase(make_pair(z,u));
}
else{
sta[alled[par[u]].getad(u)].erase(make_pair(z,u));
}
}
while((int)sta[u].size()>0&&(int)st[u].size()<i&&(*sta[u].rbegin()).first>0){
auto x=*sta[u].rbegin();
sta[u].erase(x);
st[u].insert(x);
dp0[u]+=x.first;
}
while((int)sta[u].size()>0&&(int)st[u].size()>0&&(*sta[u].rbegin()).first>(*st[u].begin()).first){
auto xa=*sta[u].rbegin();
auto x=*st[u].begin();
st[u].erase(x);
sta[u].erase(xa);
st[u].insert(xa);
sta[u].insert(x);
dp0[u]-=x.first;
dp0[u]+=xa.first;
}
if(u!=0&&(int)st[u].size()==i){
dp1[u]=dp0[u]-(*st[u].begin()).first+alled[par[u]].w;
}
else if(u==0){
dp1[u]=dp0[u];
}
else{
dp1[u]=dp0[u]+alled[par[u]].w;
}
if(u!=0){
sta[alled[par[u]].getad(u)].insert(make_pair(dp1[u]-dp0[u],u));
dp0[alled[par[u]].getad(u)]+=dp0[u];
dp1[alled[par[u]].getad(u)]+=dp0[u];
}
return ;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,std::vector<int> V,std::vector<int> W){
n=N;
for(int i=0;i<n-1;i++){
alled[i].u=U[i];
alled[i].v=V[i];
alled[i].w=W[i];
adj[alled[i].u].push_back(i);
adj[alled[i].v].push_back(i);
sum+=alled[i].w;
}
allrishe.insert(0);
aval(0,0);
vector<pair<int,int>>v;
for(int i=0;i<n;i++){
v.push_back(make_pair((int)adj[i].size(),i));
sortlen.insert(make_pair(-len[i],i));
}
sort(v.rbegin(),v.rend());
vector<long long>res(n);
res[0]=sum;
for(int i=1;i<=n-1;i++){
while((int)v.size()>0&&v.back().first<=i){
del(v.back().second,i);
v.pop_back();
}
for(auto h:sortlen){
upd(h.second,i);
fdp0[h.second]=dp0[h.second];
fdp1[h.second]=dp1[h.second];
}
res[i]=sum;
for(auto x:allrishe){
if(x==0){
res[i]-=dp0[x];
}
else{
res[i]-=max(dp0[x],dp1[x]);
}
}
}
return res;
}
