题解：P7597 「EZEC-8」猜树 加强版

· · 题解

比较经典的想到距离为 1 或者说深度相差 1 的节点是他的儿子，于是我们通过递归一层层询问下去就可以确定树的结构。

容易想到，假设我们在 u 节点有一个他子树内的所有的节点，我们询问出它所有儿子节点的子树信息，那么此时我们可以通过排除其余子节点的子树来确定一个儿子的子树，因为询问的输出次数是 40000 上面是 \mathcal{O}(n^2) 的输出次数，所以我们肯定是希望通过排除来排出子树大小最大的那个儿子节点即重儿子。

而我们实在是不能通过询问或者什么算法知道重儿子，那么我们考虑直接在 u 的子树内随机一个点，因为重儿子占得子树大小比较大，所以我们这个点在重儿子的子树内的概率是比较大的，我们再通过深度查与询问距离判断这个随机的点在哪个儿子内最后排除出来即可。

询问次数大约是个 \mathcal{O}(n \log n) 实际远远跑不满，由于我不会导数和期望证明大家感性理解一下。

:::success[Ac Code]

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long
#define _ read<int>()
#define rint register int
inline bool blank(const char &x)
{
    return !(x^13)||!(x^9)||!(x^32)||!(x^10);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();(x^-1)&&blank(x);x=gc());
}
mt19937 rnd(time(0));
const int N=5005;
int dep[N],fa[N],n;
bitset<N>vis;
inline int qry(rint u,rint v)
{   
    pc('?'),pc(' '),pc('1'),pc(' '),out(u),pc(' ');out(v);pc('\n');fflush(stdout);
    return _;
}
inline vector<int> qry1(rint x)
{
    vector<int>s;
    pc('?'),pc(' '),pc('2');pc(' '),out(x);pc('\n');
    fflush(stdout);
    rint m=_;
    for(rint i=1;i<=m;++i) s.push_back(_);
    return s;
}
vector<int>s;
inline void dfs(rint u,vector<int>s)
{
    if(s.empty()) return ;
    vector<int>son;
    for(auto x:s)
    {
        if(dep[x]-dep[u]==1) son.push_back(x),fa[x]=u;
    }
    rint h=s[rnd()%s.size()]; 
    // cerr<<h<<endl;
    shuffle(son.begin(),son.end(),rnd);
    rint hea=son.back();
    for(auto x:son)
    {
        if(x==son.back()) continue;
        if(x==h)
        {
            hea=x;break;
        }
        rint d=qry(x,h);
        if(dep[h]-dep[x]==d)
        {
            hea=x;break;
        }
    }
    for(auto x:s) vis[x]=0;
    vector<int>hs;
    vector<pair<int,vector<int>>>S;
    for(auto v:son)
    {
        if(v==hea) continue;
        auto p=qry1(v);vector<int>vp;

        for(auto x:p)
        {
            vis[x]=1;
            if(x!=v) vp.push_back(x);
        }
        S.push_back({v,vp});vp.clear();p.clear();
    }
    for(auto x:s)
    {
        if(vis[x]||x==hea) continue;
        hs.push_back(x);
    }
    for(auto &p:S)
    {
        dfs(p.first,p.second);
    }
    dfs(hea,hs);
}
signed main()
{
    n=_;
    for(rint i=2;i<=n;++i)
    {
        dep[i]=qry(1,i);
        s.push_back(i);
    }
    dfs(1,s);
    pc('!');
    for(rint i=2;i<=n;++i) pc(' '),out(fa[i]);pc('\n');fflush(stdout);
    return 0;
}

:::