「ALFR Round 5」D 游戏 题解

wmrqwq · 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);
}