#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define int long long
#define pii pair<long long, long long>
void dfs(int v, vector<vector<pii>> &g, vector<int> &p, vector<int> &e, vector<bool> &leaf) {
for (auto [u, eu] : g[v]) {
if (u != p[v]) {
p[u] = v;
e[u] = eu;
leaf[v] = 0;
dfs(u, g, p, e, leaf);
}
}
}
int find_one(int n, vector<signed> U, vector<signed> V, int A, int B, int S) {
vector<int> p(n, -1), e(n, -1);
vector<bool> leaf(n, 1);
vector<vector<pii>> g(n);
for (int i = 0; i < n - 1; i++) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
dfs(S, g, p, e, leaf);
int k = 0;
vector<int> leaves;
for (int i = 0; i < n; i++) {
if (leaf[i]) {
leaves.push_back(i);
//cout << i << " ";
k++;
}
}
//cout << "\n";
vector<signed> w(n - 1);
int zero = ask(w);
int dist = zero / A;
int l = -1, r = k;
while (r - l > 1) {
int md = (l + r) / 2;
vector<signed> w(n - 1);
for (int i = 0; i < md; i++) {
int v = leaves[i];
while (p[v] != -1 && !w[e[v]]) {
w[e[v]] = 1;
v = p[v];
}
}
if (ask(w) != dist * B) l = md;
else r = md;
}
//cout << r << "\n";
int v = leaves[l], vdist = 0;
while (p[v] != -1) {
v = p[v];
vdist++;
}
int ll = 0, rr = vdist + 1;
while (rr - ll > 1) {
int md = (ll + rr) / 2;
vector<signed> w(n - 1);
int v = leaves[l];
for (int i = 0; i < md; i++) {
w[e[v]] = 1;
v = p[v];
}
if (ask(w) == zero) ll = md;
else rr = md;
}
v = leaves[l];
for (int i = 0; i < ll; i++) {
v = p[v];
}
return v;
}
void find_pair(signed n, vector<signed> U, vector<signed> V, signed A, signed B) {
int u = find_one(n, U, V, A, B, 0);
int v = find_one(n, U, V, A, B, u);
answer(u, v);
}
