#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e14;
vector<long long> rez;
set<pair<long long,int>> con_heavy[100005],con_light[100005];
vector<int> ofsiz[100005];
bool isheavy[100005];
bool visited[100005];
long long dp[100005][2];
int degree[100005];
long long getlight(int nod, int cnt)
{
if(cnt<=0)
return 0;
if(cnt > (int)con_light[nod].size())
return INF;
auto it = con_light[nod].begin();
long long sum=0;
for(int i=0;i<cnt;i++)
{
sum += (*it).first;
it++;
}
return sum;
}
void dfs(int nod, long long up, int k)
{
visited[nod]=1;
vector<pair<long long,int>> v;
long long sum=0;
for(auto [w,x]:con_heavy[nod])
{
if(visited[x])
continue;
dfs(x,w,k);
v.push_back({dp[x][1]-dp[x][0],x});
sum += dp[x][0];
}
sort(v.begin(),v.end());
dp[nod][1]=dp[nod][0]=INF;
for(int i=0;i<=(int)v.size();i++)
{
dp[nod][0] = min(dp[nod][0], sum + getlight(nod,(degree[nod]-k)-i));
if(up!=INF) dp[nod][1] = min(dp[nod][1], sum + up + getlight(nod,(degree[nod]-k)-i-1));
if(i<(int)v.size()) sum += v[i].first;
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
rez.resize(N);
for(int i=0;i<N-1;i++)
{
con_light[U[i]].insert({W[i],V[i]});
con_light[V[i]].insert({W[i],U[i]});
}
for(int i=0;i<N;i++)
{
isheavy[i]=0;
degree[i] = con_light[i].size();
ofsiz[degree[i]].push_back(i);
}
vector<int> heavy_nodes;
for(int k=N-1;k>=0;k--)
{
for(int x:ofsiz[k+1])
{
isheavy[x]=1;
heavy_nodes.push_back(x);
set<pair<long long,int>> news;
for(auto [w,y]:con_light[x])
{
if(isheavy[y])
{
con_light[y].erase({w,x});
con_heavy[x].insert({w,y});
con_heavy[y].insert({w,x});
}
else
news.insert({w,y});
}
con_light[x] = news;
}
for(auto x:heavy_nodes)
visited[x]=0;
rez[k]=0;
for(auto x:heavy_nodes)
{
if(!visited[x])
{
dfs(x,INF,k);
rez[k] += dp[x][0];
}
}
}
/*rez[0]=0;
for(int i=0;i<N-1;i++)
rez[0] += W[i];*/
return rez;
}
