#include "roads.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(int *ww, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, w = ww[l + rand_() % (r - l)], tmp;
while (j < k)
if (ww[j] == w)
j++;
else if (ww[j] < w) {
tmp = ww[i], ww[i] = ww[j], ww[j] = tmp;
i++, j++;
} else {
k--;
tmp = ww[j], ww[j] = ww[k], ww[k] = tmp;
}
sort(ww, l, i);
l = k;
}
}
int ww[N - 1];
vl minimum_closure_costs(int n, vi uu, vi vv, vi ww_) {
vl ans(n);
int h;
for (h = 0; h < n - 1; h++)
ww[h] = ww_[h];
if (n <= 2 || uu[1] == 0) {
sort(ww, 0, n - 1);
for (h = n - 1; h >= 0; h--)
ans[h] = h == n - 1 ? 0 : ans[h + 1] + ww[n - 2 - h];
} else {
long long dp, dq, dp_, dq_;
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] = max(dp, dq);
}
return ans;
}
