#include "bits/stdc++.h"
#include "nile.h"
using namespace std;
struct DSU {
vector<int> parent;
DSU(int n) : parent(n, -1) {}
int find(int x) {
if (parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (parent[x] > parent[y]) swap(x, y);
parent[x] += parent[y];
parent[y] = x;
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size();
int Q = E.size();
// Sort artifact indices by weight
vector<int> ordW(N);
iota(ordW.begin(), ordW.end(), 0);
sort(ordW.begin(), ordW.end(), [&](int i, int j) {
return W[i] < W[j];
});
// Build edges between sorted neighbors
vector<array<int, 3>> edges;
for (int i = 0; i + 1 < N; ++i) {
int u = ordW[i], v = ordW[i + 1];
edges.push_back({abs(W[u] - W[v]), u, v});
}
for (int i = 0; i + 2 < N; ++i) {
int u = ordW[i], v = ordW[i + 2];
edges.push_back({abs(W[u] - W[v]), u, v});
}
sort(edges.begin(), edges.end());
// Sort queries by increasing D
vector<int> ordQ(Q);
iota(ordQ.begin(), ordQ.end(), 0);
sort(ordQ.begin(), ordQ.end(), [&](int i, int j) {
return E[i] < E[j];
});
vector<long long> res(Q);
DSU dsu(N);
// Keep track of which component has been merged and its cost
vector<bool> merged(N, false);
vector<vector<int>> groups(N); // group[i] holds nodes in component with root i
for (int i = 0; i < N; ++i) groups[i] = {i};
// Initial total cost: send all artifacts alone
long long total = 0;
for (int i = 0; i < N; ++i) total += A[i];
int ei = 0;
for (int qi = 0; qi < Q; ++qi) {
int d = E[ordQ[qi]];
while (ei < edges.size() && edges[ei][0] <= d) {
int u = edges[ei][1], v = edges[ei][2];
int ru = dsu.find(u);
int rv = dsu.find(v);
if (ru != rv) {
// Remove old cost
long long oldCost = 0;
if (!merged[ru]) {
if (groups[ru].size() % 2 == 0) {
for (int x : groups[ru]) oldCost += B[x];
} else {
long long minExtra = LLONG_MAX;
for (int x : groups[ru]) {
oldCost += B[x];
minExtra = min(minExtra, 1LL * (A[x] - B[x]));
}
oldCost += minExtra;
}
}
if (!merged[rv]) {
if (groups[rv].size() % 2 == 0) {
for (int x : groups[rv]) oldCost += B[x];
} else {
long long minExtra = LLONG_MAX;
for (int x : groups[rv]) {
oldCost += B[x];
minExtra = min(minExtra, 1LL * (A[x] - B[x]));
}
oldCost += minExtra;
}
}
dsu.unite(u, v);
int newRoot = dsu.find(u);
if (newRoot == rv) swap(ru, rv); // make ru the new root
for (int x : groups[rv]) groups[ru].push_back(x);
groups[rv].clear();
merged[ru] = true;
// Add new cost
long long newCost = 0;
if (groups[ru].size() % 2 == 0) {
for (int x : groups[ru]) newCost += B[x];
} else {
long long minExtra = LLONG_MAX;
for (int x : groups[ru]) {
newCost += B[x];
minExtra = min(minExtra, 1LL * (A[x] - B[x]));
}
newCost += minExtra;
}
total -= oldCost;
total += newCost;
}
++ei;
}
res[ordQ[qi]] = total;
}
return res;
}
