#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e14;
struct SegTree
{
vector<pair<int,long long>> aint;///{cnt,sum}
pair<int,long long> combine(pair<int,long long> x, pair<int,long long> y)
{
return {x.first+y.first,x.second+y.second};
}
void upd(int nod, int st, int dr, int poz, int newv)
{
if(st==dr)
{
if(newv>0) aint[nod] = {1,newv};
else aint[nod] = {0,0};
return;
}
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv);
else upd(nod*2+1,mij+1,dr,poz,newv);
aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
long long qry(int nod, int st, int dr, int k)
{
if(st==dr)
return aint[nod].second;
int mij=(st+dr)/2;
if(aint[nod*2].first >= k)
return qry(nod*2,st,mij,k);
else
return aint[nod*2].second + qry(nod*2+1,mij+1,dr,k-aint[nod*2].first);
}
};
SegTree seg[100005];
int cate[100005];
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];
map<int,int> nrm[100005];
long long getlight(int nod, int cnt)
{
if(cnt<=0)
return 0;
if(cnt > (int)con_light[nod].size())
return INF;
return seg[nod].qry(1,1,cate[nod],cnt);
}
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);
seg[i].aint.resize(4*degree[i]+2,{0,0});
cate[i]=0;
for(auto it:con_light[i])
{
nrm[i][it.second]=++cate[i];
}
for(auto it:con_light[i])
{
seg[i].upd(1,1,cate[i],nrm[i][it.second],it.first);
}
}
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});
seg[x].upd(1,1,cate[x],nrm[x][y],-1);
seg[y].upd(1,1,cate[y],nrm[y][x],-1);
}
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;
}
