题解 P7595 【猜树】

Legitimity · 2021-05-10 21:15:46 · 题解

交互题？可以乱搞，有意思

首先分别考虑只用一种询问的做法。

subtask1+2+3（？）+5

考虑询问 2，把每个节点的子树都搞下来，开这样几个东西：

这两个都可以在询问子树的时候求出来，具体做法不细讲。

然后是类似拓扑排序的思想：将所有节点按 siz 由小到大排序，前面的若干个 siz 一定是 1，即这些节点是叶子节点。这样从前到后处理，一定是按照从叶子节点向上处理的顺序。

处理到叶子节点 u 时，把 u 删除，按照 f_u 把 u 的祖先的 siz 全减一，找到祖先中 siz 最小的节点 v，则 fa_u=v。因为如果 u 的祖先 v 不是 u 的父亲的话，那么 u 真正的父亲 v' 的子树则一定是 v 的子树的子集，所以 siz_{v'}<siz_v。

这样不断向后处理，处理到 i 时，siz_i 也一定等于 1，因为它的子树已经在先前的处理中删掉了。

为什么？可以自己试着画图推一下，其实非常好理解，这里直接放一下代码：

#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,siz[2005],fa[2005];
int f[2005][2005],cnt[2005];
int no[2005];
inline bool cmp(int a,int b){
    return siz[a]<siz[b];
}
signed main(){
    n=read(); siz[1]=n; siz[n+1]=inf;  //初始化。
    for(rg int i=2;i<=n;++i){
        printf("? 2 %d\n",i); fflush(stdout);
        siz[i]=read();
        for(rg int j=1;j<=siz[i];++j){
            u=read(); if(u==i) continue;
            f[u][++cnt[u]]=i;
        }
        f[i][++cnt[i]]=1; //1 是根节点，也是所有节点的祖先。
        no[i]=i;
    }
    sort(no+2,no+1+n,cmp); //将节点按 siz 排序，依次处理。
    for(rg int g=2;g<=n;++g){
        int now=no[g];
        fa[now]=n+1;
        for(rg int i=1;i<=cnt[now];++i){
            --siz[f[now][i]];  //因为自己被删掉了，把祖先的 siz 全部减一。
            if(siz[f[now][i]]<siz[fa[now]]) fa[now]=f[now][i];  //siz 最小的就是父亲。
        }
    }
    printf("! ");
    for(rg int i=2;i<=n;++i){
        printf("%d ",fa[i]);
    }
    fflush(stdout);
    return 0;
}

时间复杂度和询问次数？这里的复杂度和子树大小递减的速度有关，同一层的节点越多，复杂度就越低，比如完全二叉树时，时间复杂度和询问次数为 \Theta(n\log n)，反之，如果为链，每次子树只递减 1，那么时间复杂度和询问次数约为 \Theta(n^2)。数据随机的情况为 \Theta(n\sqrt n)。（prufer 序列生成的真随机，下文亦同）

期望得分 [35,55]

subtask1+2+3+4

考虑询问 1。

开这样几个东西：

2. 没了

当 dis_{u,v}=1 且 dep_u>dep_v 时，fa_u=v。

（这不用我解释吧……）

那么思路就很明了了，首先询问 1 到其它节点的距离得出 dep，然后每次把已经知道父亲的节点入队（若 dep_i=1 则 fa_i=1)。对于对头的节点 v ，询问每个 dep_v+1=dep_u 的 u 节点，若 dis 为 1，则令 fa_u=v ，并把 v 入队。

代码：

#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,fa[2005],dep[2005];
int q[2005],f,r;
signed main(){
    n=read(); dep[1]=0;
    for(rg int i=2;i<=n;++i){
        printf("? 1 1 %d\n",i); fflush(stdout);
        dep[i]=read();
        if(dep[i]==1){
            fa[i]=1; q[++r]=i;
        } //处理深度和第一批入队的点。
    }
    while(f<r){
        int now=q[++f]; 
        for(rg int i=2;i<=n;++i){
            if(dep[i]==dep[now]+1&&!fa[i]){
                printf("? 1 %d %d\n",now,i); fflush(stdout);
                u=read();
                if(u==1){
                    fa[i]=now; q[++r]=i;
                }
            }
        }//对于当前节点找到其所有的儿子并入队。
    }
    printf("! ");
    for(rg int i=2;i<=n;++i){
        printf("%d ",fa[i]);
    }
    fflush(stdout);
    return 0;
}

时间复杂度和询问次数？因为这题对时间复杂度的要求不高，这里窝偷了个懒，时间复杂度是稳定的 \Theta(n^2)，但其实可以做到和询问次数同阶的。询问次数则与每一次的节点个数有关，询问次数的总数大约是 \sum dep_i\times dep_{i+1}。如果是链，询问次数达到最优的 n，如果每次的节点很多，如完全二叉树，那么询问次数将会退化到 n^2 以上。随机数据的询问次数也是 n\sqrt n 左右。

期望得分 [55,55]

接下来是乱搞环节，我们发现 n\leq 2000 相对于 10^5 来说非常小，考虑一些不太正经的解法。

可以按照当前深度的节点数 cnt[dep_i] 进行分治，如果大于阈值 T，跑第一种，反之跑第二种，时间复杂度是 \Theta(\frac{n^2}{T}+nT)。这是一个显然的根号分治，T 取 \sqrt n 时候达到最优的 \Theta(n\sqrt n)，不过这里的不再是随机数据，针对所有数据都可以做到复杂度不退化。

期望得分 [100,100]。

但还有另一种简单粗暴的写法，不如根号分治优，就是直接判断整颗树的深度，取一个阈值 T，深的话跑第二种，浅的话跑第一种，即数据分治（

我也不知道 T 取多少最好。这样的复杂只是度是比单独的两种好，但还是可以被卡掉，但是这题数据水，这样写就能过了。

期望得分 [70,100]。

代码：

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define inf 0x3f3f3f3f
#define ll long long
#define vit vector<int>::iterator
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,fa[2005],dep[2005],mxdep,siz[2005];
int f[2005][2005],cnt[2005];
int q[2005],fr,r;
int no[2005];
inline bool cmp(int a,int b){
    return siz[a]<siz[b];
}
inline void work(){
    siz[1]=n; siz[n+1]=inf;
    for(rg int i=2;i<=n;++i){
        printf("? 2 %d\n",i); fflush(stdout);
        siz[i]=read();
        for(rg int j=1;j<=siz[i];++j){
            u=read(); if(u==i) continue;
            f[u][++cnt[u]]=i;
        }
        f[i][++cnt[i]]=1;
        no[i]=i;
    }
    sort(no+2,no+1+n,cmp);
    for(rg int g=2;g<=n;++g){
        int now=no[g];
        fa[now]=n+1;
        for(rg int i=1;i<=cnt[now];++i){
            --siz[f[now][i]]; 
            if(siz[f[now][i]]<siz[fa[now]]) fa[now]=f[now][i];
        }
    }
}
signed main(){
    n=read(); dep[1]=0;
    for(rg int i=2;i<=n;++i){
        printf("? 1 1 %d\n",i); fflush(stdout);
        mxdep=max(dep[i]=read(),mxdep);
        if(dep[i]==1){
            fa[i]=1; q[++r]=i;
        }
    }
    if(mxdep<=50) //数据分治（
        work(); //第一种。
    else{  //第二种。
        while(fr<r){
            int now=q[++fr]; 
            for(rg int i=2;i<=n;++i){
                if(dep[i]==dep[now]+1&&!fa[i]){
                    printf("? 1 %d %d\n",now,i); fflush(stdout);
                    u=read();
                    if(u==1){
                        fa[i]=now; q[++r]=i;
                    }
                }
            }
        }
    }
    printf("! ");
    for(rg int i=2;i<=n;++i){
        printf("%d ",fa[i]);
    }
    fflush(stdout);
    return 0;
}