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

· · 题解

如果你直接把 P7595 的代码往这里一粘，你就可以获得 30-50 pts 的优秀分数

此做法来自月赛讲评。

看这题的数据，显然是需要一个 O(n\log n) 的做法。

考虑一个 simple idea：如果 dep_u=dep_v+1 且 u 在 v 的子树中，那么 f_u=v。

那么就有一个显然的做法：n 次询问把 dep 搞出来，然后从根节点向下递归处理每个节点，对于每个节点询问一次子树，这样做询问的量级在 O(n^2) 左右（连弱化版都过不了）。

如何改进？对于 v 节点，确定一个儿子 u。知道了 v 节点的子树，又知道了 v 其它儿子的子树，两者相减就可以得到 u 的子树。这样做，每次可以省去一个儿子的子树的询问。

那么 u 应该选哪个呢？显然应该选重儿子，在考虑树剖和 dsu on tree 里的推论，可以得到 \sum siz_i-siz_{u_i} 的量级在 O(n\log n)（证明可以去看 oiwiki），完全二叉树时达到下界。那么如果能够知道每个节点的重儿子，那么就可以在 O(n\log n) 内解决这个问题。

如何在一颗结构不明的树里找到每个节点的重儿子？随机的艺术。

我们随机一些点，根据定义，重儿子的子树最大，那么应该占随机出的点就应该更多。那么我们就把占随机点最多的儿子当成重儿子。

那么应该随机几个呢？通过实验发现，随机 1 个表现十分优秀。

为什么？随机的艺术。

复杂度的退化主要来自与处理时把重儿子和轻儿子颠倒了，如果出题人想卡这样的做法，就必须将重儿子搞得尽量重，但随即 \sum siz_i-siz_{u_i} 也会更小，所以实际表现也十分优秀。

代码：（son 表示重儿子，siz 表示子树大小，sontree 表示子树）

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define inf 0x3f3f3f3f
#define ll long long
inline int read(){
    rg int ret=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();}
    return f?-ret:ret;
}
int n,u,dep[5005],siz[5005],sontree[5005][5005],son[5005]; 
int fa[5005];
bool vis[5005];
void dfs(int x){
    if(!siz[x]) return;
    int tmp=sontree[x][rand()%siz[x]+1],cnt=0;
    random_shuffle(sontree[x]+1,sontree[x]+siz[x]+1);
    for(rg int i=1;i<=siz[x];++i){
        if(dep[sontree[x][i]]!=dep[x]+1) continue;
        if(tmp==sontree[x][i]) u=0;
        else printf("? 1 %d %d\n",sontree[x][i],tmp),fflush(stdout),u=read();
        if(u==dep[tmp]-dep[sontree[x][i]]){
            son[x]=sontree[x][i];
            break;
        }
    }//找到重儿子。 
    memset(vis,0,sizeof(vis));
    for(rg int i=1;i<=siz[x];++i){
        if(dep[sontree[x][i]]==dep[x]+1&&sontree[x][i]!=son[x]){
            printf("? 2 %d\n",sontree[x][i]); fflush(stdout);
            siz[sontree[x][i]]=read()-1;
            int cntnow=0;
            for(rg int j=1;j<=siz[sontree[x][i]]+1;++j){
                u=read(); vis[u]=1;
                if(u!=sontree[x][i]) sontree[sontree[x][i]][++cntnow]=u;
            }
        }
    }//询问轻儿子的子树 
    for(rg int i=1;i<=siz[x];++i){
        if(!vis[sontree[x][i]]&&sontree[x][i]!=son[x]) 
            sontree[son[x]][++siz[son[x]]]=sontree[x][i];
    }//根据轻儿子的子树推出重儿子的子树。 
    for(rg int i=1;i<=siz[x];++i){
        if(dep[sontree[x][i]]==dep[x]+1){
            fa[sontree[x][i]]=x;
            dfs(sontree[x][i]);
        }
    }//递归处理。 
}
signed main(){
    n=read(); 
    for(rg int i=2;i<=n;++i){
        printf("? 1 1 %d\n",i); fflush(stdout);
        dep[i]=read(); sontree[1][++siz[1]]=i;
    } //处理深度。 
    dfs(1);
    printf("! ");
    for(rg int i=2;i<=n;++i) printf("%d ",fa[i]);
    puts("");
    fflush(stdout);
    return 0;
}