Description
这是一道交互题。本题中，交互库可能是自适应的。
有一张 \(N\) 个点 \(M\) 条边的无向连通图。点编号 \(0\sim N-1\)，边编号 \(0\sim M-1\)，第 \(i\)（\(0 \leq i \leq M-1\)）条边双向连接点 \(U_i\) 和 \(V_i\)。
有一把钥匙藏在某一个点上，而有一个宝箱藏在另一个节点上。你需要通过至多 \(300\) 次询问确定钥匙所在的节点编号和宝箱所在的节点编号：
询问
对于 \(i=0,1,\ldots,M-1\)，将第 \(i\) 条边设置为单向通行。
- 具体地，构造长度为 \(M\) 的 \(01\) 序列 \(x_0\sim x_{M-1}\)。\(x_i=0\) 表示第 \(i\) 条边从 \(U_i\) 指向 \(V_i\)，\(x_i=1\) 表示第 \(i\) 条边从 \(V_i\) 指向 \(U_i\)。
交互库会返回，在这张图中，是否能从钥匙所在的节点到达宝箱所在的节点。
你需要用至多 \(70\) 次询问确定钥匙所在的节点 \(A\) 和宝箱所在的节点 \(B\)。
\(N\leq 10000,M\leq 15000\)。
Solution
先考虑树怎么做。注意到我们如果能够找到任何一个合法的定向方案使得 \(A\) 能到 \(B\)，那么把这棵树的拓扑序拿出来就能二分了。因为 \(A\) 此时拓扑序一定在 \(B\) 之前，二分找到最长的前缀 \([1,d]\)，让拓扑序数组上 \([1,d]\) 和 \([d+1,n]\) 之间的边反向，如果 \(A\) 还能到 \(B\) 就说明 \(A\) 在 \([d+1,n]\) 里，否则 \(A\) 在 \([1,d]\) 里。对 \(B\) 是同理的。
现在再来考虑怎么找到一组这样的定向方案。
对于菊花的情况，由于 \(A\) 和 \(B\) 至少有一个二进制位不同，所以选择一个二进制位，让这一位为 \(0\) 的边方向指向根，为 \(1\) 的方向指向叶子。再询问将这个图反向的结果，通过 \(2\log N\) 次询问一定能够得到满足条件的方案。
对于普通树，考虑通过点分治将问题变得类似菊花，即钦定 \(A\) 和 \(B\) 的路径经过当前的根 \(x\)，我们让 \(x\) 每个儿子子树内的边方向相同，就变成菊花了，然后让点分树同层的 \(x\) 并行做，总次数是 \(O(\log^2N)\)。
注意到 \(x\) 是重心，所以 \(x\) 儿子子树最大的大小不超过 \(\frac{sz_x}{2}\)，容易发现一定存在 \(x\) 儿子的一个划分方案使得每个集合内的子树大小和在 \(\left[\frac{sz_x}{3},\frac{2sz_x}{3}\right]\) 内，随便找到一个这样的划分，将这两个划分看成两个子树做上面的做法，再对这两个划分分治即可。
总次数为 \(2\log_{\frac{3}{2}}N+2\log_2N\)。
Code
#include "thief.h"
#include <bits/stdc++.h>#ifdef ORZXKR
#include "grader.cpp"
#endifconst int kMaxN = 6e4 + 5, kMaxM = 2e4 + 5;int n, m, rt, mxd, cnt;
int u[kMaxM], v[kMaxM], sz[kMaxN], mx[kMaxN], dep[kMaxN], real[kMaxN], now[kMaxN];
bool ont[kMaxM], del[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN], T[kMaxN];
std::vector<int> eid[kMaxN];void add(int u, int v, int id) {T[u].emplace_back(v, id), T[v].emplace_back(u, id);
}bool ask(std::vector<int> perm) {static int pos[kMaxN];std::vector<int> vec(m);for (int i = 1; i <= n; ++i) pos[perm[i - 1]] = i;for (int i = 1; i <= m; ++i) vec[i - 1] = (pos[u[i]] > pos[v[i]]);return query(vec);
}bool ask(bool *dir, bool op = 0) {std::vector<int> vec(m);for (int i = 1; i <= m; ++i) vec[i - 1] = dir[i] ^ op;return query(vec);
}struct Node {int deg[kMaxN] = {0}, _deg[kMaxN] = {0};std::vector<int> G[kMaxN];void add(int u, int v) { G[u].emplace_back(v), ++_deg[v]; }std::vector<int> getperm() {std::queue<int> q;std::vector<int> perm;for (int i = 1; i <= n; ++i) {deg[i] = _deg[i];if (!deg[i])q.emplace(i);}for (; !q.empty();) {int u = q.front(); q.pop();perm.emplace_back(u);for (auto v : G[u]) {if (!--deg[v]) q.emplace(v);}}return perm;}bool query() { return ask(getperm()); }
} gr[100];void build() {static bool vis[kMaxN];std::fill_n(vis + 1, n, 0);std::function<void(int)> dfs = [&] (int u) {vis[u] = 1;for (auto [v, id] : G[u]) {if (!vis[v]) {ont[id] = 1, T[u].emplace_back(v, id), T[v].emplace_back(u, id);dfs(v);}}};dfs(1);
}void getsz(int u, int fa) {sz[u] = 1, mx[u] = 0;for (auto [v, id] : T[u]) {if (v == fa || del[v]) continue;getsz(v, u);sz[u] += sz[v], mx[u] = std::max(mx[u], sz[v]);}
}void getrt(int u, int fa, int tot) {mx[u] = std::max(mx[u], tot - sz[u]);if (mx[u] < mx[rt]) rt = u;for (auto [v, id] : T[u]) {if (v == fa || del[v]) continue;getrt(v, u, tot);}
}void dfs(int u, int fa, int rt) {dep[u] = dep[fa] + 1;now[real[u]] = u;for (auto [v, id] : T[u]) {if (v == fa || del[v]) continue;if (id) eid[rt].emplace_back(id);dfs(v, u, rt);}
}void solve(int u, int d) {static int pid[kMaxN];mx[rt = 0] = 1e9, getsz(u, 0), getrt(u, 0, sz[u]);u = rt, dep[u] = 1, now[real[u]] = u;std::vector<int> vid;int tot = 0;for (auto [v, id] : T[u]) {if (del[v]) continue;eid[v] = (id ? std::vector<int>{id} : std::vector<int>{});pid[v] = id;vid.emplace_back(v), dfs(v, u, v);tot += eid[v].size();}std::sort(vid.begin(), vid.end(), [&] (int i, int j) { return eid[i].size() < eid[j].size(); });if (!tot) return;int id1 = 0, id2 = 0;std::vector<int> e1, e2;for (int i = 0, now = 0; i < vid.size(); ++i) {now += eid[vid[i]].size();if (now >= tot / 3) {real[id1 = ++cnt] = real[u];if (i + 1 < vid.size()) real[id2 = ++cnt] = real[u];for (int j = 0; j <= i; ++j) {int v = vid[j];for (auto id : eid[v]) e1.emplace_back(id);add(id1, vid[j], pid[vid[j]]);}for (int j = i + 1; j < vid.size(); ++j) {int v = vid[j];for (auto id : eid[v]) e2.emplace_back(id);add(id2, vid[j], pid[vid[j]]);}// std::cerr << "fuckkk " << u << ' ' << tot << ' ' << now << ' ' << tot - now << '\n';break;}}for (auto id : e1) {int x = ::u[id], y = ::v[id];if (dep[now[x]] > dep[now[y]]) std::swap(x, y);gr[2 * d - 1].add(x, y), gr[2 * d].add(y, x);}for (auto id : e2) {int x = ::u[id], y = ::v[id];if (dep[now[x]] > dep[now[y]]) std::swap(x, y);gr[2 * d - 1].add(y, x), gr[2 * d].add(x, y);}mxd = std::max(mxd, 2 * d);del[u] = 1;if (tot == 1) return;assert(id1 && id2);// std::cerr << "shabi " << u << ' ' << cnt << ' ' << d << ' ' << sz[u] << ' ' << id1 << ' ' << id2 << '\n';// std::cerr << e1.size() << ' ' << e2.size() << '\n';if (id1) solve(id1, d + 1);if (id2) solve(id2, d + 1);
}void solve(int N, int M, std::vector<int> U, std::vector<int> V) {n = N, m = M;for (int i = 1; i <= m; ++i) {u[i] = U[i - 1] + 1, v[i] = V[i - 1] + 1;G[u[i]].emplace_back(v[i], i);G[v[i]].emplace_back(u[i], i);}build();cnt = n;for (int i = 1; i <= n; ++i) real[i] = i;solve(1, 1);for (int d = 1; d <= mxd; ++d) {// std::cerr << gr[d].query() << '\n';if (gr[d].query()) {auto perm = gr[d].getperm();static int pos[kMaxN];for (int i = 1; i <= n; ++i) pos[perm[i - 1]] = i;int a = 0, b = 0;{int L = 1, R = n + 1, res = 1;while (L + 1 < R) {int mid = (L + R) >> 1;std::vector<int> vec(m);for (int i = 1; i <= m; ++i) {int x = pos[u[i]], y = pos[v[i]];if (x < mid || y < mid) vec[i - 1] = (x < y);else vec[i - 1] = (x > y);}if (query(vec)) L = res = mid;else R = mid;}a = perm[res - 1];}{int L = 0, R = n, res = n;while (L + 1 < R) {int mid = (L + R) >> 1;std::vector<int> vec(m);for (int i = 1; i <= m; ++i) {int x = pos[u[i]], y = pos[v[i]];if (x > mid || y > mid) vec[i - 1] = (x < y);else vec[i - 1] = (x > y);}if (query(vec)) R = res = mid;else L = mid;}b = perm[res - 1];}answer(a - 1, b - 1);return;}// std::cerr << gr[i].ask() << '\n';}
}