题意

给定一个联通无向图，你需要通过 $\le 70$ 次询问求出一组点对 $(a, b)$。对于一次询问，你需要为图中的每一条边定向，交互库会告诉你定向后 $a$ 是否可以到达 $b$。

题解

对于链的情况，假定 $a<b$，我们每次将左右端点都 $\le k$ 的边设为 $1$，则若此时 $a$ 仍能到达 $b$，有 $a\ge k$，$b$ 同理。通过二分即可求出 $a$，$b$，询问次数为 $2\log n$。

对于菊花图的情况，我们每次随机一半的边设为 $1$ 并询问，设此时可以到达 $0$ 的点集为 $S$，$0$ 可以到达的点集为 $T$。假设有一次询问返回 $1$，说明 $a$，$b$ 分别在 $S$，$T$ 内，然后就可以套用链的情况，每次将 $S$ 分成两个均匀的点集 $S1$ 和 $S2$，将 $S2$ 中的点与 $0$ 相连的边翻转并查询即可。询问次数期望为 $3\log n$。若将第一部分的随机点集询问改为用合并果子的方法进行询问即可将询问次数严格控制在 $3\log n$ 以内。

对于一般树的做法，我们先做一个点分治，然后即可套用菊花图的解法了。

具体地，设此时枚举中心为 $u$，我们将 $u$ 的儿子 $v$ 用合并果子的方法分成均匀的两部分 $S1$，$S2$，将 $S1$ 中的子树的边定向为父向边、叶向边，$S2$ 中子树的边定向为叶向边、父向边，两次询问后再向子树内递归即可。如果某次询问答案是 $1$，则再用 $2\log n$ 次询问二分点集求出答案即可。

发现同一层内的所有询问是可以并行的，于是总共只要询问 $3\log n$ 次。

图与树的情况类似，我们只需要先拎出来一棵生成树，最后让每次询问定向后的图能形成一个有向无环图即可。

代码

#include<bits/stdc++.h>
#include"thief.h"
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
using namespace std;
using pa=pair<int, int>;
const int N=3e4+7;
int n, m, fr[N], to[N], bel[N], cnt, nowdep;
vector<int> G[N], H[N];
void addedge(int u, int v){G[u].emplace_back(v), G[v].emplace_back(u);}
bool vis[N];
struct DAG{
  vector<int> G[N];
  int d[N];
  void init(int u, int v){++d[v], G[u].emplace_back(v);}
  vector<int> get(){
    vector<int> p(n+1, 0);
    queue<int> q;
    rep(i, 1, n) if(!d[i]) q.emplace(i);
    int cnt=0;
    while(!q.empty()){
      int u=q.front(); q.pop();
      p[u]=++cnt;
      for(auto v:G[u]) if(!--d[v]) q.emplace(v);
    }
    return p;
  }
}t[50];

void build_tree(int u){
  vis[u]=1;
  for(auto v:H[u]) if(!vis[v]){
    addedge(u, v);
    build_tree(v);
  }
}

int fa[N], siz[N], rt, mx[N], sum;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void findrt(int u, int pre){
  siz[u]=1, mx[u]=0;
  for(auto v:G[u]) if(!vis[v] && v!=pre)
    findrt(v, u), siz[u]+=siz[v], mx[u]=max(mx[u], siz[v]);
  mx[u]=max(mx[u], sum-siz[u]);
  if(!rt || mx[u]<mx[rt]) rt=u;
}

void getsiz(int u, int pre){
  siz[u]=1;
  for(auto v:G[u]) if(!vis[v] && v!=pre)
    getsiz(v, u), siz[u]+=siz[v];
}

void dfs(int u, int pre, int dep, bool flag){
  if(flag) t[dep].init(bel[pre], bel[u]);
  else t[dep].init(bel[u], bel[pre]);
  for(auto v:G[u]) if(!vis[v] && v!=pre)
    dfs(v, u, dep, flag);
}

void solve(int u, int dep){
  getsiz(u, 0), sum=siz[u];
  rt=0, findrt(u, 0), u=rt, getsiz(u, 0);
  vis[u]=1;
  priority_queue<pa, vector<pa>, greater<pa> > q;
  vector<int> son;
  for(auto v:G[u]) if(!vis[v]) q.emplace(siz[v], v), fa[v]=v, son.emplace_back(v);
  if(q.size()<=1){
    if(!q.empty()) t[dep].init(bel[u], bel[son[0]]);
    return;
  }
  while(q.size()>2){
    int u=q.top().second, x=q.top().first; q.pop();
    int v=q.top().second, y=q.top().first; q.pop();
    fa[u]=v; q.emplace(x+y, v), siz[v]=x+y;
  }
  int s1=q.top().second; q.pop(); int s2=q.top().second;
  cnt+=2, bel[cnt]=bel[cnt-1]=bel[u];
  for(auto v:son) 
    if(find(v)==s1) t[dep].init(bel[v], bel[u]), dfs(v, u, dep, 0), addedge(cnt-1, v);
    else t[dep].init(bel[u], bel[v]), dfs(v, u, dep, 1), addedge(cnt, v);
  solve(s1, dep+1), solve(s2, dep+1);
}

int Q(vector<int> &p){
  vector<int> x(m, 0);
  rep(i, 1, m) x[i-1]=p[fr[i]]>p[to[i]];
  return query(x);
}

void getans(vector<int> &p){
  vector<int> x(m, 0);
  int l=1, r=n, mid, s, t, u;
  while(l<=r){
    mid=l+r>>1;
    rep(i, 1, m) 
      if(p[fr[i]]<=mid || p[to[i]]<=mid) x[i-1]=p[fr[i]]<p[to[i]];
      else x[i-1]=p[fr[i]]>p[to[i]];
    if(!query(x)) s=mid, r=mid-1;
    else l=mid+1;
  }
  l=1, r=n;
  while(l<=r){
    mid=l+r>>1;
    rep(i, 1, m) 
      if(p[fr[i]]>=mid || p[to[i]]>=mid) x[i-1]=p[fr[i]]<p[to[i]];
      else x[i-1]=p[fr[i]]>p[to[i]];
    if(!query(x)) t=mid, l=mid+1;
    else r=mid-1;
  }
  rep(i, 1, n) if(p[i]==s){s=i; break;}
  rep(i, 1, n) if(p[i]==t){t=i; break;}
  answer(s-1, t-1);
}

void run(){
  cnt=n;
  rep(i, 1, m) H[fr[i]].emplace_back(to[i]), H[to[i]].emplace_back(fr[i]);
  build_tree(1);
  rep(i, 1, n) vis[i]=0, bel[i]=i;
  solve(1, 1);
  rep(_, 1, 40){
    vector<int> p=t[_].get();
    if(Q(p)) return getans(p);
    for(auto &x:p) x=n-x+1;
    if(Q(p)) return getans(p);
  }
}

void solve(int n, int m, vector<int> u, vector<int> v){
  ::n=n, ::m=m;
  rep(i, 1, m) fr[i]=u[i-1]+1, to[i]=v[i-1]+1;
  run();
}

写在最后

感谢 sjy 老师为笔者细致地讲解了这道题，这里强烈安利他的这篇博客，里面有这次 JOIST 几乎所有题的题解喵。

另外，都看到这里了，点个赞再走呗。