#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const long long BIG = 1000000000000000000LL;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int borne = 131*1000;
int nbNoeuds, nbAretes;
int petitCout, grosCout;
vector<int> adjAr[borne]; // Indices des ARETES
int somAr[borne]; // u+v
pii noeudsAr[borne];
vector<int> niveaux[borne];
int nbLevels = 0;
int dist = 0;
int rac = 0;
int arPar[borne];
bool interdir[borne];
void dfs(int nod, int par, int dep)
{
for (int arete : adjAr[nod]) {
int voisin = somAr[arete] - nod;
if (voisin == par) { arPar[nod] = arete; continue; }
// Ici, on ordonne parent -> enfant
if (noeudsAr[arete].fi != nod) swap(noeudsAr[arete].fi, noeudsAr[arete].se);
niveaux[dep].push_back(arete);
chmax(nbLevels, dep+1);
dfs(voisin, nod, dep+1);
}
}
vector<int> pris;
int curLeft, curRight;
void rebuild(int l1, int l2)
{
curLeft = l1; curRight = l2;
pris.assign(nbAretes, 0);
form2(lvl, l1, l2+1) {
for (int x : niveaux[lvl]) {
pris[x] = 1;
}
}
}
inline void _setNiv(int niv, int val)
{
for (int x : niveaux[niv]) pris[x] = val;
}
void ajuster(int l1, int l2)
{
while (curLeft > l1) { // On ajoute le précedent
--curLeft;
_setNiv(curLeft, 1);
}
while (curLeft < l1) { // On supprime le courant
_setNiv(curLeft, 0);
++curLeft;
}
while (curRight < l2) { // On ajoute le suivant
++curRight;
_setNiv(curRight, 1);
}
while (curRight > l2) { // On supprime le courant
_setNiv(curRight, 0);
--curRight;
}
}
int countAretes()
{
ll cx = ask(pris);
ll diffTot = cx - (ll)(dist) * petitCout;
int diffUnit = (int)(diffTot / (ll)(grosCout - petitCout));
assert(cx >= diffTot && diffUnit <= dist);
return diffUnit;
}
int hauteur = 0, ivDeb = 0, ivFin = 0;
void construireIntervalle()
{
if (hauteur == 0) {
int l = curLeft, r = curRight;
while (l < r) {
int m = (l+r+1)/2;
ajuster(m, curRight);
if (countAretes() == dist) l = m;
else r = m-1;
}
int deb = l;
ajuster(deb, curRight);
}
if (hauteur) rebuild(ivDeb, ivFin);
int deb = curLeft;
int l = curLeft, r = curRight;
while (l < r) {
int m = (l+r) / 2;
ajuster(deb, m);
int requis = dist;
if (hauteur) { requis -= (ivFin - m); }
int cnt = countAretes();
assert(cnt <= requis);
if (cnt == requis) r = m;
else l = m+1;
}
assert(deb == curLeft);
rebuild(deb, l);
}
pair<int, int> deuxAretes(int niv)
{
rebuild(niv, niv);
int totSurNiv = countAretes();
assert(totSurNiv == 1 || totSurNiv == 2);
auto &liste = niveaux[niv];
int sz = liste.size();
int l = 0, r = sz-1;
while (l < r) {
int m = (l+r+1)/2;
_setNiv(niv, 0);
form2(i, m, sz) pris[liste[i]] = 1;
if (countAretes() == totSurNiv) l = m;
else r = m-1;
}
int a1 = liste[l];
if (totSurNiv == 1) { return pii {a1, -1}; }
int relDeb = l;
r = sz-1;
while (l < r) {
int m = (l+r) / 2;
_setNiv(niv, 0);
form2(i, relDeb, m+1) pris[liste[i]] = 1;
if (countAretes() == totSurNiv) r = m;
else l = m+1;
}
int a2 = liste[l];
return pii {a1, a2};
}
void remonter(int nod, int ha)
{
form(i, ha) {
interdir[arPar[nod]] = true;
int vx = noeudsAr[arPar[nod]].fi;
assert(nod != vx);
nod = vx;
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
nbNoeuds = N;
nbAretes = U.size();
assert(nbAretes == nbNoeuds-1);
petitCout = A; grosCout = B;
pris.assign(nbAretes, 0);
form(i, nbAretes) {
somAr[i] = U[i] + V[i];
noeudsAr[i] = {U[i], V[i]};
adjAr[U[i]].push_back(i);
adjAr[V[i]].push_back(i);
}
rac = nbNoeuds/3;
if (rac) --rac;
dfs(rac, -1, 0);
rebuild(0, nbLevels-1);
dist = (int)(ask(pris) / (ll)(B));
hauteur = 0;
construireIntervalle();
hauteur = (curRight - curLeft) + 1;
assert(hauteur <= dist);
ivDeb = curLeft;
ivFin = curRight;
rebuild(ivFin, ivFin);
pii aretes = deuxAretes(ivFin);
int s1 = noeudsAr[aretes.fi].se;
remonter(s1, hauteur);
if (aretes.se != -1) {
int s2 = noeudsAr[aretes.se].se;
answer(s1, s2);
return;
}
if (hauteur == dist) {
pii wls = deuxAretes(ivDeb);
int s2 = noeudsAr[wls.fi].fi; // Parent lca
assert(wls.se == -1);
answer(s1, s2);
return;
}
construireIntervalle();
assert(curRight < ivFin);
pii wls = deuxAretes(curRight);
if (interdir[wls.fi]) swap(wls.fi, wls.se);
assert(wls.fi != -1 && interdir[wls.fi] == false && wls.se != -1 && interdir[wls.se] == true);
int s2 = noeudsAr[wls.fi].se;
answer(s1,s2);
}
