#include "nile.h"
#include <algorithm>
#include <numeric>
#include <iostream>
using namespace std;
typedef long long ll;
const ll inf = 1e9+10;
vector<ll> par;
vector<ll> mn;
vector<ll> sz;
vector<ll> sm;
ll mnz(int x)
{
return par[x] = (x==par[x]?x:mnz(par[x]));
}
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e)
{
int n = a.size();
int q = e.size();
par = vector<ll>(n, 0);
mn = vector<ll>(n, inf);
sz = vector<ll>(n, 1);
vector<ll> ixsw(n);
iota(ixsw.begin(), ixsw.end(), 0);
sort(ixsw.begin(), ixsw.end(), [&w](int i, int j)
{
return w[i] < w[j];
});
iota(par.begin(), par.end(), 0);
vector<ll> rez(q);
vector<pair<ll, ll>> qr;
for (int i = 0; i < q; i++)
qr.push_back({e[i], i});
sort(qr.begin(), qr.end());
vector<pair<ll, ll>> edges;
for (int i = 0; i+1 < n; i++)
edges.push_back({ixsw[i], ixsw[i+1]});
sort(edges.begin(), edges.end(), [&w](pair<ll, ll> i1, pair<ll, ll> i2)
{
int r1 = abs(w[i1.first]-w[i1.second]);
int r2 = abs(w[i2.first]-w[i2.second]);
return r1 < r2;
});
int j = 0;
int tre = 0;
for (int i = 0; i < n; i++){
mn[ixsw[i]] = a[ixsw[i]]-b[ixsw[i]];
tre += a[ixsw[i]];
}
for (int i = 0; i < q; i++)
{
auto [ds, ix] = qr[i];
while (j<edges.size())
{
auto [i1, i2] = edges[j];
int r = abs(w[i1]-w[i2]);
if (r > ds)
break;
int x = mnz(i1);
int y = mnz(i2);
if (x==y) continue;
if (sz[y]%2)
tre-=mn[y];
if (sz[x]%2)
tre-=mn[x];
par[y] = x;
sz[x] += sz[y];
mn[x] = min(mn[x], mn[y]);
if (sz[x]%2)
tre+=mn[x];
j++;
}
rez[ix] = tre;
}
return rez;
}
