#include "nile.h"
#include <algorithm>
#include <numeric>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll findp(vector<ll>& par, ll x) {
return par[x] == x ? x : par[x] = findp(par, par[x]);
}
vector<long long> calculate_costs(vector<int> w, vector<int> A, vector<int> B, vector<int> E) {
ll n = A.size();
ll q = E.size();
vector<ll> par(n);
vector<ll> sz(n, 1);
vector<ll> mn(n), sm(n);
for (ll i = 0; i < n; i++) {
par[i] = i;
sm[i] = (ll)A[i] - B[i]; // saving for artifact i.
mn[i] = sm[i]; // for a singleton, the min saving equals its saving.
}
ll tre = 0;
for (ll i = 0; i < n; i++) {
tre += A[i];
}
vector<ll> ixsw(n);
iota(ixsw.begin(), ixsw.end(), 0);
sort(ixsw.begin(), ixsw.end(), [&w](ll i, ll j) {
return w[i] < w[j];
});
vector<pair<ll,ll>> queries(q);
for (ll i = 0; i < q; i++) {
queries[i] = { E[i], i };
}
sort(queries.begin(), queries.end());
vector<pair<ll,ll>> edges;
for (ll i = 0; i + 1 < n; i++) {
edges.push_back({ ixsw[i], ixsw[i+1] });
}
sort(edges.begin(), edges.end(), [&w](pair<ll,ll> p1, pair<ll,ll> p2) {
return abs(w[p1.first] - w[p1.second]) < abs(w[p2.first] - w[p2.second]);
});
vector<ll> rez(q);
ll edgeIndex = 0;
for (ll i = 0; i < q; i++) {
ll d = queries[i].first;
ll qIdx = queries[i].second;
while (edgeIndex < edges.size() &&
abs(w[edges[edgeIndex].first] - w[edges[edgeIndex].second]) <= d) {
ll u = edges[edgeIndex].first;
ll v = edges[edgeIndex].second;
ll ru = findp(par, u);
ll rv = findp(par, v);
if (ru == rv) {
edgeIndex++;
continue;
}
ll disc_ru = (sz[ru] % 2 == 1) ? (sm[ru] - mn[ru]) : sm[ru];
ll disc_rv = (sz[rv] % 2 == 1) ? (sm[rv] - mn[rv]) : sm[rv];
ll oldDiscount = disc_ru + disc_rv;
if (sz[ru] < sz[rv]) {
swap(ru, rv);
}
par[rv] = ru;
sz[ru] += sz[rv];
sm[ru] += sm[rv];
mn[ru] = min(mn[ru], mn[rv]);
ll newDiscount = (sz[ru] % 2 == 1) ? (sm[ru] - mn[ru]) : sm[ru];
tre -= (newDiscount - oldDiscount);
edgeIndex++;
}
rez[qIdx] = tre;
}
return rez;
}
