Problem Link

首先我们要尝试把图上问题规约到树上，自然的想法是取出 BFS 树，如果树根在无权情况下的最短路上，那么把非树边都填 $B$ 后可以近似看作树上问题。

首先考虑如何求树根：如果把一个点集 $S$ 的所有出边都变成 $B$ 再询问最短路，就能知道是否有最短路不经过 $S$，二分出最小的一个 $k$ 使得删掉 $[1,k]$ 使最短路变化，则 $k$ 即为所求。

那么以 $k$ 为根建立 BFS 树，但为了排除非树边的影响，我们只能通过询问的答案是否等于原始最短路来进行判断。

可以直接在 BFS 序或 DFS 序上二分，给一个前缀的边集填 $A$，其他填 $B$ 就能确定起点终点是否均在该范围内，可以二分出一个端点，以该点为根重新二分一次即可得到答案。

询问次数 $3\log_2n\le 51$，可以通过二分第一个端点时的已知信息进行剪枝优化一次询问。

严谨的做法是考虑一条最短路上的边，那么 $s,t$ 只要在两侧的子树上二分，那么不可能两侧都取到 $17$ 次询问。

时间复杂度 $\mathcal O(n\log n)$。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ask(const vector<int>&w);
void answer(int s,int t);
const int MAXN=1e5+5;
namespace luotianyi {
int n,m,A,B,d[MAXN];
vector <int> L,R,q,o;
ll chk(int k) {
	for(int i=0;i<m;++i) q[i]=min(L[i],R[i])<=k;
	return ask(q);
}
bool vis[MAXN];
struct Edge { int v,id; };
vector <Edge> G[MAXN],bfn;
void bfs(int rt) {
	memset(d,0x3f,sizeof(d)),d[rt]=0;
	queue <int> Q; Q.push(rt),bfn.clear();
	while(Q.size()) {
		int u=Q.front(); Q.pop();
		for(auto e:G[u]) if(d[e.v]>d[u]+1) d[e.v]=d[u]+1,Q.push(e.v),bfn.push_back(e);
	}
}
void solve() {
	q.resize(m); ll D=chk(-1); int rt=n;
	for(int l=0,r=n-1;l<=r;) {
		int mid=(l+r)>>1;
		if(chk(mid)>D) rt=mid,r=mid-1;
		else l=mid+1;
	}
	bfs(rt);
	int s=-1,t=-1;
	for(int i=0;i<n-1;++i) if(d[bfn[i].v]<=D/A) o.push_back(i);
	for(int l=0,r=o.size()-1;l<=r;) {
		int mid=(l+r)>>1; q=vector<int>(m,1);
		for(int i=0;i<=o[mid];++i) q[bfn[i].id]=0;
		if(ask(q)==D) s=bfn[o[mid]].v,r=mid-1;
		else l=mid+1;
	}
	for(int i=0,c=0;i<n-2;++i) {
		int u=bfn[i].v; c|=u==s;
		if(d[u]!=D/A-d[s]||c) vis[u]=1;
	}
	bfs(s),o.clear();
	for(int i=0;i<n-1;++i) if(d[bfn[i].v]==D/A&&!vis[bfn[i].v]) o.push_back(i);
	for(int l=0,r=o.size()-1;l<=r;) {
		int mid=(l+r)>>1; q=vector<int>(m,1);
		for(int i=0;i<=o[mid];++i) q[bfn[i].id]=0;
		if(ask(q)==D) t=bfn[o[mid]].v,r=mid-1;
		else l=mid+1;
	}
	answer(s,t);
}
}
void find_pair(int N,vector<int>U,vector<int>V,int a,int b) {
	using namespace luotianyi;
	for(int i=0;i<(int)U.size();++i) G[U[i]].push_back({V[i],i}),G[V[i]].push_back({U[i],i});
	n=N,A=a,B=b,L=U,R=V,m=U.size(),solve();
}