自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 23:15:28，当前版本为作者最后更新于2025-04-28 16:13:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

验题人题解。

题目链接

「ALFR Round 5」D 游戏

解题思路

考虑交互库做这两种操作我们分别能得到什么信息。

如果交互库执行向 $u$ 移动一步的操作，则此时非 $u$ 的度数为 $1$ 的节点经过这一步操作后一定不是关键点 $s$，因为若关键点是这些节点，则这些节点都会向上跳一步。

如果交互库告诉你当前 $u$ 和 $s$ 的距离，设这个距离为 $d$，若 $d = 0$，则 $u$ 就是关键节点 $s$，否则，此时 $u$ 一定不是当前的关键节点 $s$。

首先特判 $n = 1$ 的情况。

我们考虑持续询问一个可能为关键点 $s$ 的度数为 $1$ 的节点。

因此如果交互库在做操作一时，此时可以直接删除树上非 $u$ 的度数为 $1$ 的节点；如果交互库在做操作二时，如果给出的距离 $d$ 为 $0$，则可以直接确定关键节点 $s = u$，否则若 $s$ 不为 $0$ 时，可以直接在树上删除 $u$ 这个节点。

注意到 $n \ge 2$ 时，树上一定有 $\ge 2$ 个度数为 $1$ 的节点。因此此时一定会询问到只剩下一个节点为止，所以这个询问策略是对的。由于每次询问至少排除一个节点，所以询问次数为 $n - 1$ 次。

参考代码

ll n,m;
ll x,y;
vector<ll>G[1000010];
ll in[1000010];
ll vis[1000010];
set<ll>v,v2;
ll S;
ll ask(ll x)
{
    cout<<"? "<<x<<endl;
    ll y;
    cin>>y;
    if(y==1)
        return -1;
    return rd();
}
void _clear(){}
void solve()
{
    _clear();
    cin>>n>>m;
    S=n;
    v.clear();
    forl(i,1,n)
        in[i]=0,
        vis[i]=0,
        G[i].clear();
    forl(i,2,n)
        cin>>x>>y,
        G[x].pb(y),
        G[y].pb(x),
        in[x]++,in[y]++;
    forl(i,1,n)
        if(in[i]==1)
            v.insert(i),
            vis[i]=1,
            S--;
    if(v.size()<1)
    {
        cout<<"! 1"<<endl;
        rd();
        return ;
    }
    while(v.size()>1)
    {
        ll now=*v.begin();
        ll num=ask(now);
        if(num==-1)
        {
            set<ll>v2;
            v2.insert(now);
            for(auto i:v)
                if(i!=now)
                    for(auto j:G[i])
                    {
                        in[j]--;
                        if(in[j]==1 && !vis[j])
                            v2.insert(j),
                            S--,
                            vis[j]=1;
                    }
            v=v2;
        }
        else
        {
            if(num==0)
            {
                v.clear();
                cout<<"! "<<now<<endl;
                if(!rd())
                    exit(-1);
                return ;
            }
            v.erase(now);
            for(auto j:G[now])
            {
                in[j]--;
                if(in[j]==1 && !vis[j])
                    v.insert(j),
                    S--,
                    vis[j]=1;
            }
        }
    }
    if(v.size()==0)
        exit(0);
    cout<<"! "<<*v.begin()<<endl;
    v.clear();
    if(!rd())
        exit(-1);
}