题目大意

有一颗编号为 $0 \sim n-1$ 的以 $0$ 为根节点 的树，树的形状大概如下图。

是由许多条链与 $0$ 节点相邻，链的长度可以为 $1$ ，但第一条也就是 $1$ 节点的链长度必须大于等于 $2$ （ $1$ 恰好与两个点相邻，其中包括 $0$ 节点）。

以 $p_{x}$ 表示 $x$ 的父亲节点，有结论 $x \le y \Rightarrow p_{x} \le p_{y}$。

这是一道交互题

对于每一次询问 $u,v$ ，

如果 $u$ 到 $v$ 的路径中有 $0$ 则返回 $1$，

如果没有 则返回 $0$ ，

不合法的询问返回 $-1$。

要求通过不超过 $2n-4$ 次询问 得到树的形状 （ $n \ge 4$ ）。

对于每一次询问输出 $“? u v”$ 的格式。

最后答案，输出 $“ ! p_{1} p_{2} \dots p_{n-1}”$ 。

题目思路

由于 以 $p_{x}$ 表示 $x$ 的父亲节点 有结论 $x \le y \Rightarrow p_{x} \le p_{y}$，

所以与 $0$ 相邻的节点必定为 $1 \sim id-1$ 是连续的（ 设 $id-1$ 为最后一个与 $0$ 相邻的节点 ）。

如果不连续的话一定会有一个值使得 $p_{x}>0$ 且 $x<id-1$ 这与题意矛盾。

所以从 $2$ 开始向后遍历，找到第一个数 $id$ 使得从 $id$ 到 $1$ 中没有 $0$ 节点，所以 $p_{id}=1$。

那么 $\forall x \in 2 \sim id-1 , 0 \le p_{x} < 1 \Rightarrow p_{x}=0$ ，那么所有的链的开头都求出来了。

所以树的形状一定可以分成分多层，每一层的数都从小到大排序对应上一层的一个数，如果上一层一个位置有空缺，那么以后那一列都不在会再有数字，如下图。

code

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int T,n,p[N],a[N];
// a[i]：开头为i的这一列的最后的点标号
bool vis[N];
// 用来标记开头为i的这一列还有没有可能有新的节点
int query(int u,int v) { // 交互
    printf("? %d %d\n",u,v);
    fflush(stdout);
    int r;
    scanf("%d",&r);
    return r;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int id; p[1]=0;
        for(int i=2;i<n;i++)
            if(!query(1,i)) { id=i; break; }
            else p[i]=0,a[i]=i,vis[i]=true; // 求出所有的开头
        vis[1]=true;
        p[id]=1; a[1]=id;
        int l=min(2,id-1),tot=id+1;
// 从2开始找因为第一行1已经有值了 但有只有1这一列的特殊情况 所以取min值
        while(tot<n) {
            do {
                while(!vis[l]) l= l==id-1 ? 1: l+1;
                // 直接跳过不可能的值减少询问次数
                if(query(l,tot)) {
                    vis[l]=false;
                    // 这一行空缺了以后这一列都不会在有新的节点
                    l= l==id-1 ? 1: l+1;
                } else break;
            } while(true);
            if(a[l]==tot-1) break;
            // 优化 如果两个连续的数连在同一列那么后面的所有数都在这一列上了
            p[tot]=a[l]; a[l]=tot++;
            l= l==id-1 ? 1 : l+1;
        }
        for(int i=tot;i<n;i++)
            p[i]=i-1;
        printf("!");
        for(int i=1;i<n;i++) printf(" %d",p[i]);
        printf("\n");
        fflush(stdout);
    }
    return 0;
}