#include "roads.h" #include <vector> using namespace std; typedef vector<int> vi; typedef vector<long long> vl; 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]; 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]; return ans; }