#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
vector<pair<ll,ll>>G[LIM], V[LIM];
vector<ll>W, S[LIM];
multiset<ll>U[LIM], NU[LIM];
ll dp[LIM][2], odw[LIM], wla[LIM], sumu[LIM], sumw, n;
void DFS(int x, int o, int k) {
odw[x]=1;
ll sum0=0;
vector<ll>D;
for(auto i : V[x]) if(i.st!=o) {
DFS(i.st, x, k);
sum0+=dp[i.st][0];
D.pb(dp[i.st][1]-dp[i.st][0]);
}
sort(all(D));
reverse(all(D));
int d=min(k, (int)V[x].size())+1;
while(D.size()<d-1) D.pb(-INF);
vector<ll>potem;
vector<ll>X(d+1);
rep(i, d+1) {
while(U[x].size()>0 && U[x].size()>k-i) {
auto it=U[x].begin();
auto a=*it;
U[x].erase(it);
potem.pb(a);
sumu[x]-=a;
}
X[i]=sumu[x];
}
for(auto i : potem) {
U[x].insert(i);
sumu[x]+=i;
}
vector<ll>P(d);
P[0]=sum0;
rep(i, d-1) P[i+1]=P[i]+D[i];
rep(i, d) if(i<k) dp[x][1]=max(dp[x][1], P[i]+X[i+1]);
rep(i, d) dp[x][0]=max(dp[x][0], P[i]+X[i]);
for(auto i : V[x]) if(i.st==o) dp[x][1]+=i.nd;
}
ll licz(ll k) {
for(auto i : S[k]) {
wla[i]=1;
W.pb(i);
for(auto j : G[i]) {
if(wla[j.st]) {
V[i].pb(j);
V[j.st].pb({i, j.nd});
if(NU[j.st].find(j.nd)!=NU[j.st].end()) NU[j.st].erase(NU[j.st].find(j.nd));
else {
U[j.st].erase(U[j.st].find(j.nd));
sumu[j.st]-=j.nd;
}
} else {
NU[i].insert(j.nd);
sumw+=j.nd;
}
}
}
for(auto i : W) {
odw[i]=0;
dp[i][0]=dp[i][1]=-INF;
while(U[i].size()>k) {
auto it=U[i].begin();
auto a=*it;
sumu[i]-=a;
U[i].erase(it);
NU[i].insert(a);
}
while(U[i].size()<k && NU[i].size()>0) {
auto it=NU[i].end(); --it;
auto a=*it;
sumu[i]+=a;
U[i].insert(a);
NU[i].erase(it);
}
}
ll ans=0;
for(auto i : W) if(!odw[i]) {
DFS(i, i, k);
ans+=dp[i][0];
}
return ans;
}
vector<ll>minimum_closure_costs(int _n, vector<int>_U, vector<int>_V, vector<int>_W) {
n=_n;
rep(i, n-1) {
G[_U[i]].pb({_V[i], _W[i]});
G[_V[i]].pb({_U[i], _W[i]});
}
rep(i, n) S[G[i].size()].pb(i);
vector<ll>wynik(n);
for(int i=n-1; i>=0; --i) {
ll x=licz(i);
wynik[i]=sumw-x;
}
return wynik;
}
