#include "highway.h" #include <bits/stdc++.h> #define ll long long #define ii pair<int,int> #define fi first #define se second #define pb push_back using namespace std; vector<vector<ii> > vec; vector<int> query; vector<ii> target; ll dist,a,b; void dfs(int node,ll d,int high,int p){ if(d*a==dist){ target.pb(ii(high,node)); return; } for(auto child:vec[node]) if(child.fi!=p) dfs(child.fi,d+1,child.se,node); } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { int M = U.size(); a=A,b=B; vec.resize(N); query.resize(M); for (int i = 0; i < M; ++i) { vec[U[i]].pb(ii(V[i],i)); vec[V[i]].pb(ii(U[i],i)); } fill(query.begin(),query.end(),0); dist=ask(query); dfs(0,0,-1,0); sort(target.begin(),target.end()); int l=0,r=(int)target.size()-1,ans=0; while(l<=r){ int med=(l+r)>>1; fill(query.begin(),query.end(),0); for (int i = l; i <= med; ++i) query[target[i].fi]=1; ll check=ask(query); if(check!=dist){ ans=med; r=med-1; } else l=med+1; } answer(0, target[ans].se); }