#include "roads.h"
#include <stdlib.h>
#include <vector>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
long long max(long long a, long long b) { return a > b ? a : b; }
const int N = 100000;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
void sort(long long *aa, int l, int r) {
while (l < r) {
int i = l, j = l, k = r;
long long a = aa[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[j] == a)
j++;
else if (aa[j] < a) {
tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
i++, j++;
} else {
k--;
tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
}
sort(aa, l, i);
l = k;
}
}
int ii[N - 1], jj[N - 1], ww[N - 1];
int *eh[N], eo[N];
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
long long xx[N], dp[N], dq[N]; int k;
void dfs(int p, int i) {
int o, m, h;
long long x;
x = 0;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (j != p) {
dfs(i, j);
x += dp[j];
}
}
m = 0;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (j != p)
xx[m++] = dq[j] + ww[h] - dp[j];
}
sort(xx, 0, m);
dp[i] = x;
for (h = m - 1; h >= 0 && h >= m - k && xx[h] > 0; h--)
dp[i] += xx[h];
dq[i] = x;
for (h = m - 1; h >= 0 && h >= m - (k - 1) && xx[h] > 0; h--)
dq[i] += xx[h];
}
vl minimum_closure_costs(int n, vi ii_, vi jj_, vi ww_) {
vl ans(n);
int h, i, star, path;
for (h = 0; h < n - 1; h++)
ii[h] = ii_[h], jj[h] = jj_[h], ww[h] = ww_[h];
star = 1;
for (h = 0; h < n - 1; h++)
if (ii[h] != 0) {
star = 0;
break;
}
path = 1;
for (h = 0; h < n - 1; h++)
if (ii[h] != h || jj[h] != h + 1) {
path = 0;
break;
}
if (star) {
for (h = 0; h < n - 1; h++)
xx[h] = ww[h];
sort(xx, 0, n - 1);
for (h = n - 1; h >= 0; h--)
ans[h] = h == n - 1 ? 0 : ans[h + 1] + xx[n - 2 - h];
} else if (path) {
long long dp, dq, dp_, dq_;
for (h = 0; h < n; h++)
ans[h] = 0;
for (h = 0; h < n - 1; h++)
ans[0] += ww[h];
dp = ww[0], dq = 0;
for (h = 1; h < n - 1; h++)
dp_ = dq + ww[h], dq_ = max(dp, dq), dp = dp_, dq = dq_;
ans[1] = ans[0] - max(dp, dq);
} else {
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (h = 0; h < n - 1; h++)
append(ii[h], h), append(jj[h], h);
for (h = 0; h < n - 1; h++)
ans[0] += ww[h];
for (k = 1; k < n; k++) {
dfs(-1, 0);
ans[k] = ans[0] - dp[0];
}
}
return ans;
}
