P12421

2021CHD · 2025-05-06 15:17:43 · 题解

注意事项

这是一道交互题，注意刷新缓存区。

对于 C++ 语言，推荐使用 endl 换行以刷新缓存区。

题目大意

给出 n 个点的树，树上有一个关键点 s，操作至多 n-1 次，每次选择一个点 u，交互库每次可以选择将 s 向 u 移动一步（s=u 则不移动）或给出 s 到 u 的距离，最后需求出点 s 当前的位置，有多测。

解法

不妨称交互库的两种行为分别为“移动”或“回复”。

观察不难发现“移动”将会带来更少的信息，首先考虑如果交互库一直“移动”我们要如何应对。

不难发现我们只要每次指定相同的 u，那么 n-1 次操作后一定有 s=u。方便起见我们将题目中给出的树视为以 u 为根的有根树。

那么如果某次交互库选择“回复”，那么我们不可能再次操作 u 了，因为交互库可以再次选择“回复”，而我们没有收到任何新的信息，相当于浪费了一次操作。

于是一旦某次交互库选择“回复”，那么我们考虑在接下来的操作中只需维护 s 的深度 t 以及 s 可能处在的子树的根节点 v，初始时有 v=u，t=d+1。

接下来从 u 开始进行一次 dfs，维护出每个点的深度（记为 h_i）以及每个点为根的子树中有多少深度为 d+1 的点（记为 w_i）。（注意不需要维护每个点为根的子树中有多少深度为 t 的点，即 t 改变时无需重新 dfs）

经过以上预处理后即可重复以下过程直到返回答案：

1. 若 h_v=t，则直接返回 v。
2. 否则，枚举 v 的每个 w_p 非 0 的子节点 p 并检查 s 是否在 p 子树内。
   • 若 p 是最后一个被检查的子节点，直接将 v 置为 p 并返回第 1 步。
   • 否则不断对 p 操作直到进行了 t-h_v+1 次或交互库选择了“回复”，期间交互库一定选择了“移动”，此时将 t 置为 t-1 即可。
   • 结束对 p 的操作后，有以下几种情况：
     • 进行了 t-h_v+1 次操作后交互库仍未选择“回复”：此时直接返回 p 即可。
     • 在第 t-h_v+1 次操作时交互库才选择“回复”：此时若 d=0，返回 p；否则 d=1，返回 v。
     • 交互库提前选择了“回复”：此时若 d=t-h_v-1，则将 v 置为 p 并返回第 1 步；否则 d=t-h_v+1，则可以判定 s 不在 p 子树内，继续枚举下一个 p 即可。

不难发现上述过程一定能正确求解出 s 当前的位置。

次数分析

不难发现上述做法在某些情况下次数可能达到 n，比如当原树为以 u 为中心的至少有 3 个节点的菊花，并且 s\neq u 时，交互库可以不断选择“回复”直到只剩 2 个可能的节点 x 和 y，并且我们尝试操作 x，那么此时交互库再选择“移动”，我们就耗尽了 n-1 次操作的机会，而需要一次额外的操作才能求出 s 当前的位置。

不难发现当 u 为叶节点时，上述情况就不会发生。（分析见下）

那么接下来分析交互次数：

• 一开始操作点 u 时，交互库每“移动”一次，至少有 1 个节点被排除了。（除非当前可能的 s 只剩 u，但是这种情况并不重要，因为反正最多也就 n-1 次操作）
• 若交互库第一次“回复”时就只有一个可能的 s，那么此时我们显然不会再进行任何更多的操作，所以这种情况也是合标的。
• 否则如果上述条件均成立（u 为叶节点且交互库第一次“回复”时有多于一个可能的 s），那么第一次“回复”时至少排除了 2 个点（u 和与 u 相邻的唯一的点）
• 接下来每步操作几乎都至少排除了 1 个点：交互库始终提前选择“回复”，那么这里每次“移动”都等价于是最开始操作点 u 时的移动，而每次“回复”都能至少排除 1 个节点，由于最后还剩 1 个节点，所以这里至多就是 n-2 次操作（第一次“回复”时多排除了 1 个点）。
• 否则一旦出现进行第 t-h_v+1 次操作的情况就会立刻求解出答案，所以这里至多比上面多出 1 步，也就是 n-1 步。

综上，本做法完全满足本题的要求，且时空复杂度均容易做到 O(\sum n)。

参考代码

这是我的赛时 AC 记录中的代码。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int T,I,n,m,u[110000],v[110000],num[110000],*mp[110000],deep[110000],siz[110000],fa[110000],d,i,j,op,x,o,pans,t;
void dfs(int x)
{
    int i;
    deep[x]=deep[fa[x]]+1;
    for(i=1;i<=mp[x][0];i++)
    if(mp[x][i]!=fa[x])
    {
        fa[mp[x][i]]=x;
        dfs(mp[x][i]);
        siz[x]=siz[x]+siz[mp[x][i]];
    }
    if(deep[x]==d)
    siz[x]++;
}
main()
{
    cin>>T;
    for(I=1;I<=T;I++)
    {
        cin>>n>>m;
        for(i=1;i<n;i++)
        cin>>u[i]>>v[i];
        for(i=1;i<n;i++)
        {
            num[u[i]]++;
            num[v[i]]++;
        }
        for(i=1;i<=n;i++)
        {
            mp[i]=new int[num[i]+1];
            mp[i][0]=0;
        }
        for(i=1;i<n;i++)
        {
            mp[u[i]][0]++;
            mp[u[i]][mp[u[i]][0]]=v[i];
            mp[v[i]][0]++;
            mp[v[i]][mp[v[i]][0]]=u[i];
        }
        for(i=1;i<=n;i++)
        if(num[i]<=1)
        break;
        o=i;
        for(i=1;i<=n-1;i++)
        {
            cout<<"? "<<o<<endl;
            cin>>op;
            if(op==2)
            {
                cin>>x;
                break;
            }
        }
        if(i>n-1)
        {
            cout<<"! "<<o<<endl;
            cin>>x;
            for(i=1;i<=n;i++)
            {
                num[i]=0;
                delete [] mp[i];
            }
            continue;
        }
        d=x+1;
        fa[o]=0;
        dfs(o);
        pans=siz[o];
        while(1)
        {
            if(deep[o]==d)
            {
                cout<<"! "<<o<<endl;
                cin>>x;
                break;
            }
            for(i=1;i<=mp[o][0];i++)
            if(mp[o][i]!=fa[o]&&siz[mp[o][i]]>0)
            if(siz[mp[o][i]]==pans)
            {
                o=mp[o][i];
                break;
            }
            else
            {
                t=d-deep[o]+1;
                for(j=1;j<=t;j++)
                {
                    cout<<"? "<<mp[o][i]<<endl;
                    cin>>op;
                    if(op==1)
                    d--;
                    else
                    {
                        cin>>x;
                        if(x==d-deep[mp[o][i]])
                        {
                            pans=siz[mp[o][i]];
                            o=mp[o][i];
                            op=3;
                            break;
                        }
                        if(j==t)
                        {
                            if(x==0)
                            cout<<"! "<<mp[o][i]<<endl;
                            else
                            cout<<"! "<<o<<endl;
                            cin>>x;
                            op=4;
                            break;
                        }
                        break;
                    }
                }
                if(op>2)
                break;
                if(j>t)
                {
                    cout<<"! "<<mp[o][i]<<endl;
                    cin>>x;
                    op=4;
                    break;
                }
                pans=pans-siz[mp[o][i]];
            }
            if(op==4)
            break;
        }
        for(i=1;i<=n;i++)
        {
            siz[i]=0;
            num[i]=0;
            delete [] mp[i];
        }
    }
}

碎碎念

怎么和官方题解做法完全不一样？

别忘了刷新缓存区，多测别忘清，别忘记读入每组数据给出答案后的 1。

赛时调了好久最后发现是 lca 挂了，一怒之下把 lca 删了，发现做法还是对的。（猜猜我一开始哪里用了 lca）