CF2001C Guess The Tree

传送门

Solution

初始化 $V_1=1$，其余 $V_i=0$，? 1 2 加入询问队列。

每次从队头取出询问 ? u v （保证 $V_u=1$，$V_v=0$），返回的结果是 $u$，$v$ 路径的中点 $p$。

1. 若 $V_p=0$，则将 ? u p 加入队列。
2. 若 $V_p=1$，则将 ? p v 加入队列。
3. 特殊地，若 $p=u$，则记录 $u$，$v$ 有边连接，不加入新的询问到队列。

如果队列为空，且确定的边数量不足 $n-1$，则遍历找出一个 $V_i=0$ 的点 $i$，并把 ? 1 i 加入队列。

其实本质就是对 $V_i$ 不同的两个点 $u$、$v$，二分找出两点路径上最靠近 $u$ 的点 $i$ 且 $V_i=0$，并更改 $V_i=1$，让 $i$ 与路径上的前一个点建边。

因此最坏情况下，每 $\log n$ 次询问就会建一条边，总询问次数大约在 $n\log n\le 15000$ 级别，满足题目要求。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, vis[N], ans_cnt, T, res;
pair<int, int> ans[N];
queue<pair<int, int> > q;

void solve()
{
    ans_cnt = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    while (q.size()) q.pop();
    q.push({1, 2});
    vis[1] = 1;
    while (q.size() && ans_cnt < n - 1) {
        int u = q.front().first, v = q.front().second;
        q.pop();
        printf("? %d %d\n", u, v);
        fflush(stdout);
        scanf("%d", &res);
        if (res == -1) exit(0);
        if (res == u) {
            vis[v] = 1;
            ans[++ans_cnt] = {u, v};
        } else {
            if (vis[res])
                q.push({res, v});
            else
                q.push({u, res});
        }
        if (q.empty()) {
            for (int i = 2; i <= n; i++) {
                if (!vis[i]) {
                    q.push({1, i});
                    break;
                }
            }
        }
    }
    printf("! ");
    fflush(stdout);
    for (int i = 1; i <= ans_cnt; i++) {
        printf("%d %d ", ans[i].first, ans[i].second);
        fflush(stdout);
    }
    putchar('\n');
    fflush(stdout);
}

int main()
{
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}