#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a, b;
vector<int> u;
vector<int> v;
const int N = 90000;
int edges;
ll minCost;
vector<int> adj[N];
vector<int> adj2[N];
void addInSubtree(int node, int par, vector<int>& w)
{
for (int i : adj2[node])
{
w[i] = 1;
}
for (int next : adj[node])
{
if (next == par) continue;
addInSubtree(next, node, w);
}
}
ll subtreeCost(int node, int par)
{
vector<int> w(m);
addInSubtree(node, par, w);
return ask(w);
}
void addEnds(int node, int par, int needed, int ch, vector<int>& possEnds)
{
if (ch == needed)
{
possEnds.push_back(node);
return;
}
for (int next : adj[node])
{
if (next == par) continue;
addEnds(next, node, needed, ch + 1, possEnds);
}
}
int getIn(vector<int>& nodes)
{
int from = 0;
int to = nodes.size() - 1;
int res = -1;
vector<int> w(m);
while (from <= to)
{
int mid = (from + to) / 2;
w.clear();
w.resize(m);
for (int i = 0; i <= mid; i++)
{
for (int j : adj2[nodes[i]])
{
w[j] = 1;
}
}
ll cur = ask(w);
if (cur == minCost)
{
from = mid + 1;
} else
{
res = nodes[mid];
to = mid - 1;
}
}
return res;
}
int getSubtreeEnd(int node, int par)
{
ll cost = subtreeCost(node, par);
int needed = (cost - minCost) / (b - a);
vector<int> possEnds;
addEnds(node, par, needed, 1, possEnds);
int res = getIn(possEnds);
return res;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
n = N;
a = A;
b = B;
u = U;
v = V;
m = v.size();
for (int i = 0; i < m; i++)
{
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
adj2[u[i]].push_back(i);
adj2[v[i]].push_back(i);
}
vector<int> w(m);
minCost = ask(w);
edges = minCost / a;
int from = 0;
int to = n - 2;
int res = -1;
while (from <= to)
{
int mid = (from + to) / 2;
w.clear();
w.resize(m);
for (int i = 0; i <= mid; i++)
{
w[i] = true;
}
ll cur = ask(w);
if (cur == minCost)
{
from = mid + 1;
} else
{
res = mid;
to = mid - 1;
}
}
int x = u[res];
int y = v[res];
int rx = getSubtreeEnd(x, y);
int ry = getSubtreeEnd(y, x);
answer(rx, ry);
}
/*
15 14 1 2 0 3
0 4
4 5
4 3
12 3
3 7
7 8
8 11
8 10
6 13
6 14
6 9
3 6
2 3
10 1
*/
