思路很自然的一道交互，赛场上都没来得及细做 QwQ。
首先询问树形态的交互题有一个非常通用的思路：剥叶子。应用在这个题上来后你马上就会发现这是好的，因为在本题中叶子有一个关键性质：只有一条邻边操控，如果这条邻边往外指那么这个点的答案一定是 \(1\)。
你会发现一个点答案是 \(1\) 的条件非常苛刻：需要其所有邻边都往外指，假设每一次询问都是纯随机的，那么叶子的答案是 \(1\) 的会大致占半数，而其它的小于半数。
我们考虑精细化设计这个策略让其变成确定性的。这个就是神隐的技巧，我们为每条边设计一个长度为 \(T=50\)，恰好有 \(\frac{T}{2}=25\) 个 \(1\) 的二进制数 \(msk_i\)，当对应 \(msk_i\) 的第 \(j\) 为 \(1\) 时我们第 \(j\) 次询问中翻转边 \(i\)。
我们只需要让这些二进制数互不相同，两两不为互补，这样的话假设一个度数至少为二的点来说，其为 \(1\) 的询问至少是 \(msk_1\cap msk_2\) 或者 \(msk_1\cap \overline{msk_2}\) 类似的形式，由于取交的两个元素不相等，其二进制下 \(1\) 的个数小于一半。所以我们只需要看哪些点恰好 \(\frac{T}{2}\) 次答案为 \(1\) 这些点就是叶子。
接下来是为这个叶子找到父亲以及找到连接它们的边。找相邻的边直接看一下其为 \(1\) 的位置与那条边的 \(msk\) 符合就行了。找父亲看起来需要一定的技巧。我们考虑当叶子不为的答案 \(1\)，其答案一定是父亲的答案加上 \(1\)。我们可以猜测如果一个点满足其一直是叶子的答案减一，那么其大概率唯一而且就是这个叶子的父亲。
为啥呢？因为一个不是父亲的点想通过度数伪装成父亲是很难的，我们的 \(msk_i\) 对于每条边每次询问都是均匀的，而每修改一条边，其相邻两个点的度数一定会变化。就算最极端的情况，设我们寻找答案为 \(goal\) 的父亲，一个点修改一次变成 \(goal\)，再修改一次一定不是 \(goal\)，再修改一次可能又变成 \(goal\)……而修改与否都是 \(\frac{1}{2}\) 随机发生的，次数奇偶性也是随机的。这样不是父亲的点答案 \(=goal\) 的概率再怎么也不会超过 \(\frac{1}{2}\)，整体至多有 \(2^{-\frac{T}{2}}\) 的错误率。
再考虑时间复杂度的事情，有人说你这代码三重循环乘起来 \(O(n^2T)\) 爆炸了啊？怎么能过呢？
事实上我们暴力 check 一个点在所有合法询问中是否都有答案 \(=goal\)，如果其不是真正的父亲，失败的概率会达到 \(\frac{1}{2}\)，这样期望 check 常数次就会退出，期望复杂度 \(O(n^2)\) 可以通过。
注意剥完一个叶子的时候，需要修改所有的询问对应的答案。一种方法是给每个点每次询问维护一个点权，表示删去的点中有多少可以到达它，然后把上述的所有 \(1\) 改成对应点权。
代码内置交互库，添加 LOCAL 宏就可以启用。
#include <map>
#include <cstdio>
#include <random>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
typedef long long ll;
mt19937 rng(random_device{}());
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=10003,T=50;
const ll MS=(1ll<<T)-1;
int n;
int eu[N],ev[N];ll msk[N];
int d[T][N],w[T][N],cnt[N];
namespace grader{
#define fi first
#define se second
typedef pair<int,int> pii;
pii e[N];
void gen(){
for(int i=1;i<n;++i){
e[i].fi=rng()%i+1;
e[i].se=i+1;
if(rng()&1) swap(e[i].fi,e[i].se);
}
shuffle(e+1,e+n,rng);
for(int i=1;i<n;++i) printf("(%d->%d) ",e[i].fi,e[i].se);
putchar('\n');
}
vector<int> vec[N];
int dfs(int u){
int res=1;
for(int v:vec[u]) res+=dfs(v);
return res;
}
void ask(int x){
putchar('?');putchar(' ');
for(int i=1;i<n;++i)
if(msk[i]>>x&1) putchar('1');
else putchar('0');
putchar('\n');fflush(stdout);
#ifdef LOCAL
for(int i=1;i<n;++i)
if(msk[i]>>x&1) vec[e[i].fi].emplace_back(e[i].se);
else vec[e[i].se].emplace_back(e[i].fi);
for(int i=1;i<=n;++i) d[x][i]=dfs(i);
for(int i=1;i<=n;++i) vec[i].clear();
#else
for(int i=1;i<=n;++i) d[x][i]=read();
#endif
}
void check(){
for(int i=1;i<n;++i) assert(eu[i]==e[i].fi&&ev[i]==e[i].se);
}
#undef fi
#undef se
}
map<ll,int> mp;
ll gen(){
int a[T];
for(int i=0;i<T;++i) a[i]=2*i<T;
shuffle(a,a+T,rng);
ll cur=0;
for(int i=0;i<T;++i) cur=cur<<1|a[i];
return cur;
}
bool del[N];
int main(){
n=read();
#ifdef LOCAL
grader::gen();
#endif
for(int i=1;i<n;++i){
ll x=gen();
while(mp.find(x)!=mp.end()) x=gen();
mp.emplace(x,i);mp.emplace(MS^x,-i);msk[i]=x;
}
for(int t=0;t<T;++t){
grader::ask(t);
for(int i=1;i<=n;++i) w[t][i]=1,cnt[i]+=(d[t][i]==1);
}
for(int it=1;it<n;++it){
int x,y;
for(int i=1;i<=n;++i)
if(!del[i]&&cnt[i]==(T>>1)){x=i;break;}
ll cur=0;
for(int t=0;t<T;++t)
if(d[t][x]==w[t][x]) cur|=(1ll<<t);
for(y=1;y<=n;++y){
if(del[y]) continue;
bool fl=0;
for(int t=0;t<T;++t){
if(cur>>t&1) continue;
if(d[t][x]==d[t][y]+w[t][x]) continue;
fl=1;break;
}
if(fl) continue;
break;
}
del[x]=1;cnt[y]=0;
for(int t=0;t<T;++t){
if(cur>>t&1) w[t][y]+=w[t][x];
cnt[y]+=(d[t][y]==w[t][y]);
}
int ps=mp[cur];
if(ps>0) eu[ps]=y,ev[ps]=x;
else eu[-ps]=x,ev[-ps]=y;
}
#ifdef LOCAL
grader::check();
#endif
putchar('!');
for(int i=1;i<n;++i) printf(" %d %d",eu[i],ev[i]);
putchar('\n');fflush(stdout);
return 0;
}