#include "roads.h"
using namespace std;
#include <vector>
#define vll vector<ll>
#define ll long long
#include <algorithm>
#include <set>
#include <queue>
#define vi vector<int>
#define pll pair<ll,ll>
#define x first
#define y second
#define pi pair<int,int>
const int siz = 1e5 + 1;
set<ll> s[siz];
priority_queue<ll> pq1[siz], pq2[siz];
bool bad[siz];
vector<pi> fr[siz];
vi his[siz];
ll sum[siz];
vll dp1[siz];
vll dp2[siz];
int deg[siz];
int w[siz][12];
vll ans;
vector<bool> vis[siz];
void dfs(int i, int k) {
if (bad[i] || vis[i][k])return;
vis[i][k] = 1;
int s = fr[i].size();
vll op;
//for (int i = 1; i <= 10; i++)op.push_back(i);
for (int j = s - 1; j >= 0; j--) {
int f = fr[i][j].x;
if (bad[f]) {
swap(fr[i][j], fr[i].back());
fr[i].pop_back();
}
else {
if (!vis[f][k]) {
dfs(f, k);
dp1[i][k] += dp1[f][k];
dp2[i][k] += dp1[f][k]; // full price
op.push_back({ fr[i][j].y + dp2[f][k] - dp1[f][k] });
}
}
}
sort(op.begin(), op.end());
op.push_back(1e9);
int mon = deg[i] - k-1;
int it = 0;
while (op[it] < 0) {
dp1[i][k] += op[it];
dp2[i][k] += op[it];
it++;
mon--;
}
ll pl = 1e9;
for (int j = 1; j <= 10; j++) {
while (op[it] < j && mon>0 ) {
dp1[i][k] += op[it];
dp2[i][k] += op[it];
it++;
mon--;
}
int m = min(mon, w[i][j]);
mon -= m;
if (w[i][j] > m)pl = min(pl, (ll)j);
dp1[i][k] += m*j;
dp2[i][k] += m*j;
}
pl = min(pl, op[it]);
dp1[i][k] += pl;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
vi cur;
ans.resize(N);
for (int i = 0; i < N - 1; i++) {
ans[0] += W[i];
fr[U[i]].push_back({ V[i],W[i] });
fr[V[i]].push_back({ U[i],W[i] });
}
for (int i = 0; i < N; i++)his[fr[i].size()].push_back(i);
for (int i = 0; i < N; i++)cur.push_back(i);
for (int i = 0; i < N; i++) {
deg[i] = fr[i].size();
dp1[i].resize(fr[i].size());
dp2[i].resize(fr[i].size());
vis[i].resize(fr[i].size());
}
for (int k = 1; k < N-1; k++) {
for (int i : his[k]) {
bad[i] = 1;
for (pll f : fr[i]) {
w[f.x][f.y]++;
}
}
int s = cur.size();
for (int i = s - 1; i >= 0; i--) {
if (bad[cur[i]]) {
swap(cur[i], cur.back()); cur.pop_back();
}
else {
if (!vis[cur[i]][k]) {
dfs(cur[i], k);
ans[k] += dp1[cur[i]][k];
}
}
}
}
return ans;
}
