#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
int n, m, h[maxn], par[maxn], edge[maxn][2], cnt;
vector<int> g[maxn];
vector<int> cand;
ll query1(int x){
cnt++;
if (cnt > 60) assert(0);
//debug(x);
vector<int> q(m, 0);
for (int i = 0; i < n; i++){
if (h[i] >= x) q[par[i]] = 1;
}
//for (int i = 0; i < m; i++) debug(i, q[i]);
return ask(q);
}
ll query2(int x){
cnt++;
if (cnt > 60) assert(0);
//debug(x);
vector<int> q(m, 0);
for (int i = 0; i <= x; i++){
q[par[cand[i]]] = 1;
}
//debug()
return ask(q);
}
void dfs(int v, int x = -1){
par[v] = x;
//debug(v, h[v], par[v]);
for (auto i: g[v]){
if (i == x) continue;
int u = edge[i][0]^edge[i][1]^v;
h[u] = h[v] + 1;
dfs(u, i);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
m = U.size();
for (int i = 0; i < m; i++){
edge[i][0] = U[i];
edge[i][1] = V[i];
g[U[i]].push_back(i);
g[V[i]].push_back(i);
}
dfs(0);
int mx = max_element(h, h+n) - h;
ll dis = query1(n);
//debug(dis);
int l = 0, r = h[mx]+1;
while(l + 1 < r){
int mid = (l + r) >> 1;
if (query1(mid) > dis) l = mid;
else r = mid;
}
//debug(l);
for (int i = 0; i < n; i++) if (h[i] == l) cand.push_back(i);
//for (auto x: cand) debug(x);
l = -1, r = cand.size() - 1;
while(l + 1 < r){
int mid = (l + r) >> 1;
if (query2(mid) > dis) r = mid;
else l = mid;
}
int r1 = cand[r];
//debug(r1);
h[r1] = 0;
dfs(r1);
//debug(l);
cand.clear();
for (int i = 0; i < n; i++) if (1ll * h[i] * a == dis) cand.push_back(i);
l = -1, r = cand.size() - 1;
while(l + 1 < r){
int mid = (l + r) >> 1;
if (query2(mid) > dis) r = mid;
else l = mid;
}
int r2 = cand[r];
//debug(r2);
answer(r1, r2);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:104:47: error: 'a' was not declared in this scope
104 | for (int i = 0; i < n; i++) if (1ll * h[i] * a == dis) cand.push_back(i);
| ^
