Luogu7597 猜树 | Arahc's Home

题面

简化题意

给一个 $1$ 为根的有根树。你可以查询两点距离（消耗 $1$ 代价）或一个点的子树（消耗子树大小的代价）。你需要消耗 $\leq 40000$ 代价还原这个树。

$n\leq 5000$ 。

题解

首先询问每个点到根的距离求 $dep$ 。考虑 dsu on tree，已知 $u$ 子树和 $u$ 除了一个儿子 $v$ 之外的儿子的子树，就能得到 $v$ 子树。

然而并不能像 dsu 一样找到重儿子——我们并不知道树的结构。考虑随机。

如果一个点的子树最大，那么如果我随机若干个点作为标记点，这个点的子树中就会有期望更多的标记点。这个时候我们令占标记点最多的点为重儿子。

那么应该随机几个呢？最好还是简单为好，为了避免两个点所占的标记点一样多导致冲突，直接只随机一个点就可以了。

这样子的算法非常玄学。但是其复杂度退化的原因就在于我随机的时候并没有找到重儿子。实际测试的时候发现即使我找到的点大部分都是轻儿子，复杂度的退化也并不明显。

再者，如果要卡掉这种随机算法，要从两个方面考虑：一个是加多轻儿子数量，另一个就是让其因为找到轻儿子复杂度退化更加明显。

选择加多轻儿子数量，可以众生平等开完美多叉树，但这样又可以视为每个点都是重儿子，而且如果一个点的儿子个数 $>2$ ，复杂度甚至会比还要小。就算开的是完美二叉树，他的复杂度也是 $\log_2 n$ 的。显然轻儿子数量越多，重儿子和轻儿子的子树大小差值也会变小，整体效率还是非常可观的。

那么还有一个方法就是让找到轻儿子复杂度的退化加剧，这样做就只能不断加大重儿子的子树大小，让其拉开和轻儿子子树大小的差距。实际上如果重儿子子树大小和轻儿子差距越大，那么每一次随机点我找到重儿子的概率也会越大。考虑到 $n$ 虽然不大，但是也不是很小，可以估算找到重儿子的次数是非常可观的。

于是我们大概口糊了一下算法的正确性，交上去是可以 AC 的。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=5050;
inline int ask1(int i,int j){
    printf("? 1 %d %d\n",i,j);
    fflush(stdout);
    int dis;
    scanf("%d",&dis);
    return dis;
}
inline int ask2(int x){
    printf("? 2 %d\n",x);
    fflush(stdout);
    int size;
    scanf("%d",&size);
    return size;
}

int n,d[max_n],s[max_n],t[max_n][max_n],hs[max_n],f[max_n];
bool b[max_n];

inline void dfs(int u){
    if(!s[u]) return;
    int p=t[u][rand()%s[u]+1];
    for(register int i=1;i<=s[u];++i){
        int v=t[u][i];
    
        if(d[v]!=d[u]+1) continue;

        int dis;
        if(v==p) dis=0;
        else dis=ask1(v,p);
        if(d[p]-d[v]==dis){
            hs[u]=t[u][i];
            break;
        }
    }

    memset(b,0,sizeof(b));
    for(register int i=1;i<=s[u];++i){
        int v=t[u][i];
        if(d[v]!=d[u]+1) continue;
        if(v==hs[u]) continue;

        s[v]=ask2(v);
        int _n=0;
        for(register int j=1;j<=s[v];++j){
            int x;
            scanf("%d",&x);
            if(x!=v) t[v][++_n]=x;
            b[x]=1;
        }
        --s[v];
    }

    for(register int i=1;i<=s[u];++i){
        int v=t[u][i];
        if(b[v]) continue;
        if(v==hs[u]) continue;
        t[hs[u]][++s[hs[u]]]=v;
    }
    for(register int i=1;i<=s[u];++i){
        int v=t[u][i];
        if(d[v]!=d[u]+1) continue;
        f[v]=u;
        dfs(v);
    }
}

signed main(){
    scanf("%d",&n);
    for(register int i=2;i<=n;++i){
        d[i]=ask1(1,i)+1,
        t[1][++s[1]]=i;
    }
    d[1]=1;
    dfs(1);
    
    printf("! ");
    for(register int i=2;i<=n;++i) printf("%d ",f[i]);
    printf("\n");
    fflush(stdout);
    return 0;
}