#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
mt19937 gen;
const ll Nm = 1e5+5; ll N;
const ll K = 200; //sqrt(N)
ll ans[Nm];
vector<pii> adj[Nm];
vector<ll> fadj[Nm];
ll deg[Nm];
pii radj[Nm]; //{number, cost}
vector<ll> itpl; //inverse topological sort
ll dp0[Nm]; //no path up
ll dp1[Nm]; //path up
ll qsel(ll nv, vector<ll> v0) { //quickselect bottom nv elements
if (nv==0) {
return 0;
}
vector<ll> v1,v2; ll neq=0; //bottom, top, # equal
ll s1=0,s2=0;
ll x = v0[gen()%(v0.size())];
for (ll y: v0) {
if (y<x) {
v1.push_back(y);
s1+=y;
} else if (y>x) {
v2.push_back(y);
s2+=y;
} else {
neq++;
}
}
if ((v1.size()+neq)<=nv) {
return (s1+x*neq+qsel(nv-v1.size()-neq,v2));
} else if (v1.size()>nv) {
return qsel(nv,v1);
} else {
return (s1+x*(nv-v1.size()));
}
}
ll slvH(ll k) { //O(NlogN) independent of k
for (ll i=(N-1);i>=0;i--) {
ll x = itpl[i];
vector<ll> vaug; //augment vector
ll val0 = 0; //minimum value
for (ll y: fadj[x]) {
val0 += dp0[y];
vaug.push_back(dp1[y]-dp0[y]);
}
//sort(vaug.begin(),vaug.end()); //can upgrade quicksort -> quickselect for true O(N)
ll NDEL = max(0LL,deg[x]-k);
dp0[x]=val0+qsel(NDEL,vaug);
NDEL = max(0LL,deg[x]-k-1);
dp1[x]=val0+radj[x].second+qsel(NDEL,vaug);
if (x!=0) {
dp0[x]=min(dp1[x],dp0[x]);
}
}
return dp0[0];
}
bool isH[Nm]; //is heavy? (aka deg>=K)
ll degL[Nm]; //light degree
vector<ll> aggL[Nm]; //light aggregates (choose x edges -> give cost)
vector<ll> elemL[Nm];
vector<pii> adjH[Nm];
pii radjH[Nm]; //heavy radj
vector<ll> fadjH[Nm]; //heavy fadj
vector<bool> foundH;
// ll gcalc(ll ndel, vector<ll> vaug, ll x) {
// vector<ll> vnew = vaug;
// for (ll y: elemL[x]) {
// vnew.push_back(y);
// }
// sort(vnew.begin(),vnew.end());
// ll vnewv = 0;
// for (ll i=0;i<ndel;i++) {
// vnewv += vnew[i];
// }
// return vnewv;
// }
ll gcalc(ll ndel, vector<ll> vaug, ll x) {
if (ndel==0) {return 0;}
if (elemL[x].size()==0 || ((vaug.size()>=ndel)&&(vaug[ndel-1]<=elemL[x][0]))) {
ll y = 0;
for (ll i=0;i<ndel;i++) {
y += vaug[i];
}
return y;
}
ll y=0; ll nfv=0; //total value, number from vaug
while (nfv<vaug.size()) {
if (nfv == ndel) {
return y;
}
auto A0 = upper_bound(elemL[x].begin(),elemL[x].end(),vaug[nfv]);
ll d0 = distance(elemL[x].begin(),A0); //# of elements <= vaug[nfv]
if ((d0+nfv+1)<=ndel) {
y += vaug[nfv];
nfv++;
} else {
return (y+aggL[x][ndel-nfv]);
}
}
return (aggL[x][ndel-nfv]+y);
}
ll slvL(ll k, vector<ll> rtpl /*reverse topological sort*/) { //O(SIZElogN) but need preprocessing -> only works for k>=K
for (ll i=(rtpl.size()-1);i>=0;i--) {
ll x = rtpl[i];
vector<ll> vaug;
ll val0 = 0;
for (ll y: fadjH[x]) {
val0 += dp0[y];
vaug.push_back(dp1[y]-dp0[y]);
}
sort(vaug.begin(),vaug.end());
dp0[x] = val0+gcalc(max(0LL,deg[x]-k),vaug,x);
dp1[x] = val0+radjH[x].second+gcalc(max(0LL,deg[x]-k-1),vaug,x);
if (i!=0) {
dp0[x]=min(dp1[x],dp0[x]);
}
}
return dp0[rtpl[0]];
}
vector<ll> minimum_closure_costs(int N1, vector<int> U, vector<int> V, vector<int> W) {
gen = mt19937((long long) new char);
N=N1;
for (ll i=0;i<N;i++) {
adj[i].clear();
fadj[i].clear();
}
itpl.clear();
ll sroad = 0;
for (ll i=0;i<(N-1);i++) {
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
sroad += W[i];
}
for (ll i=0;i<N;i++) {
deg[i]=adj[i].size();
}
queue<ll> q0;
q0.push(0); //root is 0
radj[0]={-1,-1};
while (!q0.empty()) {
ll x = q0.front(); q0.pop();
itpl.push_back(x);
for (pii p0: adj[x]) {
if (p0.first!=radj[x].first) {
fadj[x].push_back(p0.first);
radj[p0.first]={x,p0.second};
q0.push(p0.first);
}
}
}
for (ll i=0;i<N;i++) {
isH[i]=(deg[i]>=K);
radjH[i]={-1LL,-1LL};
}
for (ll i=0;i<N;i++) {
if (!isH[i]) {
continue;
}
vector<ll> iadjL; //values
for (pii p0: adj[i]) {
ll x = p0.first;
if (isH[x]) {
adjH[i].push_back(p0);
} else {
iadjL.push_back(p0.second);
}
}
degL[i]=iadjL.size();
sort(iadjL.begin(),iadjL.end());
elemL[i]=iadjL;
aggL[i].push_back(0);
ll cv = 0;
for (ll x: iadjL) {
cv += x;
aggL[i].push_back(cv);
}
}
foundH = vector<bool>(N,0);
vector<vector<ll>> itplsH; //heavy inverse topological sort
for (ll i=0;i<N;i++) {
if (!isH[i] || foundH[i]) {
continue;
}
queue<ll> q1;
q1.push(i);
vector<ll> vtc;
while (!q1.empty()) {
ll x = q1.front(); q1.pop();
foundH[x]=1;
vtc.push_back(x);
for (pii p0: adjH[x]) {
if (p0.first!=radjH[x].first) {
fadjH[x].push_back(p0.first);
radjH[p0.first]={x,p0.second};
q1.push(p0.first);
}
}
}
itplsH.push_back(vtc);
}
for (ll k=1;k<K;k++) {
ans[k]=slvH(k);
}
for (ll k=K;k<N;k++) {
ans[k]=0;
for (auto A0: itplsH) {
ans[k] += slvL(k,A0);
}
}
ans[0]=sroad;
vector<ll> ansF(N,0);
for (ll i=0;i<N;i++) {
ansF[i]=ans[i];
}
return ansF;
}
