题解：P17121 [ICPC 2025 Shanghai R] Menji, we miss you!

· · 题解

本题思维链较长，我们一步一步来。

思路一：

深度：

我们知道 1 是整棵树的根节点，知道这颗树的形状，相比，我们是可以得出一些基础性质。

树的基础性质之中较为常用的就是深度，我们考虑从 1 点（这里我们认为根节点深度为 0）发射信号，多次尝试就可以得出目标深度，这会为我们提供极大地便利。

至于发射信号的范围，我们利用二分，就可以在 \log n 次询问中得到深度。

寻找目标节点：

知道目标的深度后，我们想，可以从根节点出发，逐步向着下面探路。

举个简单的例子：

我们以样例一的第一组数据来看，通过二分得出目标节点深度为 2。

接着，我们往下探路，到了节点 2 我们要确定是否目标节点的某个祖先是 2。

由于我们已知目标节点的深度为 2，而 2 的深度为 1，倘若 2 是目标节点的祖先，则它们之间的距离一定是 1，否则一定大于 1，在样例中，查询成立，说明这一步走对了。

接着到 4，其深度与目标节点一致，问题就是：? 4 0。我们得到的结果是否定的，则应该是另一条路，就是 5 了，所以答案是 5。（这就没有查询的必要了）

每一层都要询问一次，这是一棵二叉树，完全二叉树深度为 \log n，似乎可以？

代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,f[30005],s1[30005],s2[30005],l,r,mid,x,deep,y;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        for(int i=2;i<=n;i++){
            scanf("%d",&f[i]);
            if(!s1[f[i]])s1[f[i]]=i;
            else s2[f[i]]=i;       //转换格式，求每个节点的左右孩子，便于后面计算。
        }
        l=-1;
        r=n+1;
        while(l<r-1){
            mid=(l+r)/2;
            printf("? 1 %d\n",mid);fflush(stdout);
            scanf("%d",&x);
            if(x)r=mid;
            else l=mid;
        }          //二分求目标节点深度。
        deep=r;
        y=1;
        while(deep){
            deep--;
            if(s2[y]){
                printf("? %d %d\n",s1[y],deep);fflush(stdout);
                scanf("%d",&x);
                if(x)y=s1[y];    //选择的路正确。
                else y=s2[y];    //选择的路不对，换另一条。
            }
            else{
                y=s1[y];
            }           //如果只有一个孩子，则没有询问的必要。
        }                  //向下探路。
        printf("! %d\n",y);fflush(stdout);
    }
    return 0;
}

代码写出来后提交，结果却是 WA 了，在第五个测试点。

思路二：

现在我们重新考虑一下，前面代码逻辑没有问题，但是 WA，本题是交互题，则很大概率是超出次数了。

重新寻找目标节点：

原本的逻辑是每层一次，但是，本题的二叉树不一定是完全二叉树，有可能是这样的：

像这样层数极多，并且每个点都有两个孩子的情况下，我们是最坏的，这样可以有大约 \frac{n}{2} 层，而 n \le 3\times 10^4，非常不友好。

对于这种情况，每次询问两边所含有的可能结果完全不同，比如探路到 3 ，结果在 12 和 13 中，也就是深度为 6，我们两边可能得结果数量分别是 0 和 2，非常不划算，我们最好是对半取，这样的类似二分的方法就可以完成 \log n 次询问出答案。

具体实现，我们应该统计每个点底下有多少个可能得结果（也就是深度就是目标节点深度的点），不断往下走，直到基本对半的点进行询问，如果结果是 1，说明答案就在这之下，我们可以以这个点重新为根节点探路，总可能答案数就为这个点之下的可能答案数量。反之，我们这个节点及以下删掉，更新其祖先之下可能答案数量，最后返回根节点，继续探路。

总的思想类似树的重心，总询问次数大约 2 \times \log n，是可以过的。

代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,f[30005],s1[30005],s2[30005],l,r,mid,x,deep,y,dep[30005],tot[30005],total,root;
void dfs(int x,int y){
    dep[x]=y;
    if(s1[x])dfs(s1[x],y+1);
    if(s2[x])dfs(s2[x],y+1);
}        //预处理深度。
int search(int x){
    if(dep[x]==deep){
        tot[x]=1;
        return 1;
    }
    else{
        if(s1[x]&&s2[x])tot[x]=search(s1[x])+search(s2[x]);
        else if(s1[x])tot[x]=search(s1[x]);
        else if(s2[x])tot[x]=search(s2[x]);
        return tot[x];
    }
}      //计算可能答案数。
void fan(int x){
    if(f[x]!=x)fan(f[x]);
    tot[x]-=tot[y];
}    //修改可能答案数。
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        memset(tot,0,sizeof(tot));
        memset(dep,0,sizeof(dep));
        for(int i=2;i<=n;i++){
            scanf("%d",&f[i]);
            if(!s1[f[i]])s1[f[i]]=i;
            else s2[f[i]]=i;
        }
        l=-1;
        r=n+1;
        while(l<r-1){
            mid=(l+r)/2;
            printf("? 1 %d\n",mid);fflush(stdout);
            scanf("%d",&x);
            if(x)r=mid;
            else l=mid;
        }
        deep=r;
        dfs(1,0);
        search(1);
        total=tot[1];
        root=1;
        y=root;
        for(int i=1;i<=n;i++){
            if(tot[s2[i]]>tot[s1[i]])swap(s2[i],s1[i]);
        }     //小技巧，可能答案多的放在左孩子，走也是走这条。
        while(total>1){
            while(tot[y]>(total+1)/2){
                y=s1[y];
            }
            printf("? %d %d\n",y,deep-dep[y]);fflush(stdout);
            scanf("%d",&x);
            if(x){
                total=tot[y];
                root=y;
                f[y]=y;
            }     //探路正确。
            else{
                s1[f[y]]=s2[f[y]];
                s2[f[y]]=0;
                fan(y);
                y=root;
                total=tot[root];
            }      //探路错误。
        }
        while(dep[y]!=deep){
            y=s1[y];
        }     //走到答案。
        printf("! %d\n",y);fflush(stdout);
    }
    return 0;
}

于是顺利 AC。