比赛当时降智了,没有想出来。
我们询问一个点,与它距离为 \(1\) 的所有点都跟它有边。
所以,我们想知道树的所有边只需查询所有深度为奇数的点,或所有深度为偶数的点就可以了。
这样我们就可以先查询任意一个节点,把它拉出来作根,然后再比较深度为奇数的点的个数和深度为偶数的点的个数(注意不要把根节点算进去),然后取小的那个去查询就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int h[2];
vector<int> v[2], ans[N];
int main() {
int n;
cin >> n;
cout << "? " << 1 << endl;
fflush (stdout);
for (int i = 1; i <= n; i++) {
int dep;
cin >> dep;
if (dep == 1) ans[1].push_back(i);
if (dep != 0) {
h[dep&1]++;
v[dep&1].push_back(i);
}
}
int k=0;
if (h[0] > h[1]) k = 1;
for (int i : v[k]) {
cout << "? " << i << endl;
fflush (stdout);
for (int j = 1; j <= n; j++) {
int dep;
cin >> dep;
if (dep == 1)ans[i].push_back(j);
}
}
cout << "!" << endl;
for (int i = 1; i <= n; i++)
for (int j : ans[i])
if (j != 1)
cout<<i<<" "<<j<<endl;
return 0;
}