/*
#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int Nmin = 100000;
#define int long long
const int INFINI = 1000000000000;
struct T {
int normal, enPair;
T()
{
normal = 0;
enPair = 0;
}
bool operator<(const T &other) const {
if(normal != other.normal)
return normal < other.normal;
else
return enPair > other.enPair;
}
T(int a, int b)
{
normal = a;
enPair = b;
}
};
bool existe[Nmin][2];
vector<pair<int, pair<int, int>>> aretes;
int boss[Nmin];
bool bout[Nmin];
T minRouge[Nmin], minNoir[Nmin];
pair<int, T> infos[Nmin];//W, A, B
int sommeB[Nmin];
int sommeTotal;
int taille[Nmin];
int sommeComposante[Nmin];
int findBoss(int noeud)
{
if(boss[noeud] == noeud)
{
return noeud;
}
return boss[noeud] = findBoss(boss[noeud]);
}
void comparerBalance(int noeud)
{
minRouge[findBoss(noeud)] = min(minRouge[findBoss(noeud)], infos[noeud].second);
minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], infos[noeud].second);
}
void faire(int bossA, int bossB, bool inverserCouleur)
{
if(inverserCouleur)
{
minRouge[bossA] = min(minRouge[bossA], minNoir[bossB]);
minNoir[bossA] = min(minNoir[bossA], minRouge[bossB]);
}
else
{
minRouge[bossA] = min(minRouge[bossA], minRouge[bossB]);
minNoir[bossA] = min(minNoir[bossA], minNoir[bossB]);
}
}
void merge(int a, int b)
{
cout << "hdjlkhskj" << endl;
int bossA = findBoss(a), bossB = findBoss(b);
cout << bossA << " " << bossB << endl;
if(bossA == bossB)
{
int balance = a+1;
comparerBalance(balance);
sommeTotal -= sommeComposante[bossA];
}
else
{
cout << "kjhdkjhdkjhskjhdskjhsdjskhkdjsh" << endl;
bool debutB = bout[bossB];
if(taille[bossB]%2 == 0) debutB = !debutB;
if(bout[bossA] == debutB)
faire(bossA, bossB, 1);
else
{
faire(bossA, bossB, 0);
}
if(taille[bossB]%2 == 1)
{
bout[bossA] = !bout[bossA];
}
sommeB[bossA] += sommeB[bossB];
cout << taille[bossA] << " " << taille[bossB] << endl;
taille[bossA] += taille[bossB];
cout << taille[bossA] << endl;
sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
boss[bossB] = bossA;
// cout << boss[2] << endl;
}
int noeud = bossA;
cout << sommeTotal << endl;
if(taille[noeud]%2 == 0)
{
cout << "pair <" << endl;
sommeComposante[noeud] = sommeB[noeud];
sommeTotal += sommeComposante[noeud];
cout << sommeTotal << endl;
cout << "fin" << endl;
return;
}
if(bout[noeud] == 0)
{
sommeComposante[noeud] = sommeB[noeud]-minRouge[noeud].enPair +minRouge[noeud].normal;
sommeTotal += sommeComposante[noeud];
}
else
{
sommeComposante[noeud] = sommeB[noeud]-minNoir[noeud].enPair +minNoir[noeud].normal;
sommeTotal += sommeComposante[noeud];
}
cout << sommeTotal << endl;
cout << "fin" << endl;
}
pair<int, int> requetes[Nmin];
#undef int
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
#define int long long
sommeTotal = 0;
int Q = (int)E.size();
int N = W.size();
for(int i = 0; i < Q; i++)
{
requetes[i] = {E[i], i};
}
sort(requetes, requetes+Q);
for(int i = 0; i < N; i++)
{
infos[i] = {W[i], T(A[i], B[i])};
}
sort(infos, infos+N);
for(int i = 1; i < N; i++)
{
aretes.push_back({infos[i].first-infos[i-1].first, pair<int, int>(i-1, i)});
if(i >= 2)
aretes.push_back({infos[i].first-infos[i-2].first, pair<int, int>(i-2, i)});
}
sort(aretes.begin(), aretes.end());
//aVoir
for(int i = 0; i < N; i++)
{
boss[i] = i;
taille[i] = 1;
sommeTotal += infos[i].second.normal;
sommeB[i] = infos[i].second.enPair;
sommeComposante[i] = infos[i].second.normal;
if(i % 2 == 0)
{
minRouge[i] = T(infos[i].second.normal, infos[i].second.enPair);
minNoir[i] = T(0,0);
bout[i] = 0;
continue;
}
minNoir[i] = T(infos[i].second.normal, infos[i].second.enPair);
minRouge[i] = T(0,0);
bout[i] = 1;
}
for(int i = 0; i< N; i++)
{
cout << minRouge[i].normal << " " << minNoir[i].normal << " | ";
}
cout << endl;
cout << sommeTotal << endl;
std::vector<long long> R(Q);
int iEnlever = 0;
cout << "jhkjhl" << endl;
for(int i = 0; i < Q; i++)
{
cout << "deb" << endl;
int D = requetes[i].first;
cout << D << endl;
while((iEnlever < Q) && (aretes[iEnlever].first <= D))
{
cout << aretes[iEnlever].second.first << " " << aretes[iEnlever].second.second << endl;
merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
cout << taille[findBoss(aretes[iEnlever].second.first)] << " " << minRouge[findBoss(aretes[iEnlever].second.first)].normal << " " << minNoir[findBoss(aretes[iEnlever].second.first)].normal << endl;
cout << sommeTotal << endl;
iEnlever++;
}
cout << sommeTotal << endl;
R[requetes[i].second] = sommeTotal;
}
return R;
}
/*/
#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int Nmin = 100000;
#define int long long
const int INFINI = 1000000000000;
struct T {
int normal, enPair;
T()
{
normal = 0;
enPair = 0;
}
bool operator<(const T &other) const {
if(normal != other.normal)
return normal < other.normal;
else
return enPair > other.enPair;
}
T(int a, int b)
{
normal = a;
enPair = b;
}
};
bool existe[Nmin][2];
vector<pair<int, pair<int, int>>> aretes;
int boss[Nmin];
bool bout[Nmin];
int minRouge[Nmin], minNoir[Nmin];
pair<int, T> infos[Nmin];//W, A, B
int sommeB[Nmin];
int sommeTotal;
int taille[Nmin];
int sommeComposante[Nmin];
int findBoss(int noeud)
{
if(boss[noeud] == noeud)
{
return noeud;
}
return boss[noeud] = findBoss(boss[noeud]);
}
void comparerBalance(int noeud)
{
minRouge[findBoss(noeud)] = min(minRouge[findBoss(noeud)], abs(infos[noeud].second.normal-infos[noeud].second.enPair));
minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], abs(infos[noeud].second.normal-infos[noeud].second.enPair));
}
void faire(int bossA, int bossB, bool inverserCouleur)
{
if(inverserCouleur)
{
minRouge[bossA] = min(minRouge[bossA], minNoir[bossB]);
minNoir[bossA] = min(minNoir[bossA], minRouge[bossB]);
}
else
{
minRouge[bossA] = min(minRouge[bossA], minRouge[bossB]);
minNoir[bossA] = min(minNoir[bossA], minNoir[bossB]);
}
}
void merge(int a, int b)
{
//cout << "hdjlkhskj" << endl;
int bossA = findBoss(a), bossB = findBoss(b);
// cout << bossA << " " << bossB << endl;
if(bossA == bossB)
{
int balance = a+1;
comparerBalance(balance);
sommeTotal -= sommeComposante[bossA];
}
else
{
// cout << "kjhdkjhdkjhskjhdskjhsdjskhkdjsh" << endl;
bool debutB = bout[bossB];
if(taille[bossB]%2 == 0) debutB = !debutB;
if(bout[bossA] == debutB)
faire(bossA, bossB, 1);
else
{
faire(bossA, bossB, 0);
}
if(taille[bossB]%2 == 1)
{
bout[bossA] = !bout[bossA];
}
sommeB[bossA] += sommeB[bossB];
// cout << taille[bossA] << " " << taille[bossB] << endl;
taille[bossA] += taille[bossB];
// cout << taille[bossA] << endl;
sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
boss[bossB] = bossA;
// cout << boss[2] << endl;
}
int noeud = bossA;
// cout << sommeTotal << endl;
if(taille[noeud]%2 == 0)
{
// cout << "pair <" << endl;
sommeComposante[noeud] = sommeB[noeud];
sommeTotal += sommeComposante[noeud];
// cout << sommeTotal << endl;
//cout << "fin" << endl;
return;
}
if(bout[noeud] == 0)
{
sommeComposante[noeud] = sommeB[noeud]+minRouge[noeud];
sommeTotal += sommeB[noeud]+minRouge[noeud];
}
else
{
sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud];
sommeTotal += sommeB[noeud]+minNoir[noeud];
}
//cout << sommeTotal << endl;
//cout << "fin" << endl;
}
pair<int, int> requetes[Nmin];
#undef int
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
#define int long long
sommeTotal = 0;
int Q = (int)E.size();
int N = W.size();
for(int i = 0; i < Q; i++)
{
requetes[i] = {E[i], i};
}
sort(requetes, requetes+Q);
for(int i = 0; i < N; i++)
{
infos[i] = {W[i], T(A[i], B[i])};
}
sort(infos, infos+N);
for(int i = 1; i < N; i++)
{
aretes.push_back({infos[i].first-infos[i-1].first, pair<int, int>(i-1, i)});
if(i >= 2)
aretes.push_back({infos[i].first-infos[i-2].first, pair<int, int>(i-2, i)});
}
sort(aretes.begin(), aretes.end());
//aVoir
for(int i = 0; i < N; i++)
{
boss[i] = i;
taille[i] = 1;
sommeTotal += infos[i].second.normal;
sommeB[i] = infos[i].second.enPair;
sommeComposante[i] = infos[i].second.normal;
if(i % 2 == 0)
{
minRouge[i] = abs(infos[i].second.normal - infos[i].second.enPair);
minNoir[i] = INFINI;
bout[i] = 0;
continue;
}
minNoir[i] = abs(infos[i].second.normal- infos[i].second.enPair);
minRouge[i] = INFINI;
bout[i] = 1;
}
//cout << endl;
//cout << sommeTotal << endl;
std::vector<long long> R(Q);
int iEnlever = 0;
// cout << "jhkjhl" << endl;
for(int i = 0; i < Q; i++)
{
//cout << "deb" << endl;
int D = requetes[i].first;
// cout << D << endl;
//
while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
{
//cout << aretes[iEnlever].second.first << " " << aretes[iEnlever].second.second << endl;
merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
//cout << taille[findBoss(aretes[iEnlever].second.first)] << " " << minRouge[findBoss(aretes[iEnlever].second.first)] << " " << minNoir[findBoss(aretes[iEnlever].second.first)] << endl;
//cout << sommeTotal << endl;
iEnlever++;
}
// cout << sommeTotal << endl;
R[requetes[i].second] = sommeTotal;
}
return R;
}
/** */
