题解：CF1990E1 Catch the Mole(Easy Version)

题目大意

给定一颗有 n 个节点的有根树，有一只鼹鼠在某一个节点。

每次可以进行一种询问 ? u，交互库会返回鼹鼠是不是在 u 的子树内，如果是就返回 1，否则返回 0。

同时如果询问时鼹鼠不在根且交互库返回了 0，鼹鼠会移动到父节点。

你有 300 次询问的机会，需要得到鼹鼠当前所在的节点。

题目解析

这是一种与官方题解不同的做法

考虑已经知道鼹鼠 u 的子树里如何处理。

不如将问题简化，假设我们已经知道了鼹鼠在 u 的父节点到 u 的某个祖先 v 的链上如何处理。

如果这条链比较短，我们可以直接每次询问 u 直到鼹鼠不在 v 的子树内，然后显然可以方便地求出鼹鼠的位置，需要 2*len 次询问，其中 len 是链长。

经验告诉我们，链长的 len 应该是 O(\sqrt n) 的。

考虑如何求出这条根号长的链。

我们可以将 u 的子树内距离 u 的距离为 \sqrt n 的节点取出，然后递归到子问题，这样链长度就是根号的了。

然而如果你这样写了并且提交，你会在 pretest 48 或 test 71 挂掉，因为这个做法实在太好卡了，直接在一个菊花上伸出一条长度为 \sqrt n-1 的链连到根，就可以把询问次数卡到 n+\sqrt n，不如暴力，咳咳。

考虑优化这个过程。

因为我们不要求链长度是严格的 \sqrt n，所以可以考虑贪心地去扩链的长度，如果深度 +1 可以使得需要询问的点数变少，就贪心的将深度 +1，这样链长最多为 \sqrt n *2。

然鹅这个做法依然很好卡，考虑每根号个节点挂一个两层的菊花，且第一层的点数是第二层的点数 -1，这样大约可以卡到 \frac n 3 次询问左右。

这个贪心做法很有启发性，感觉很有前途，于是我们可以去取一个区间 [L,R]，在与当前节点 u 的深度差属于 [\sqrt n \cdot L,\sqrt n \cdot R] 的节点集合里取最小的，这样就卡不掉一丁点了，实测 L=0.8, R=1.3 时询问次数是 280 次左右，可以通过此题。

Code

赛时代码改的，可能比较混乱。

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
auto checkml(int u){
    cout<<format("? {}",u)<<'\n';
    cout.flush();
    int tp;cin>>tp;
    return tp;
}
auto answer(int u){
    cout<<format("! {}",u)<<'\n';
    cout.flush();
}
class check{
private:
    vector<vector<int>> gr,hx;
    vector<int> dfn,rdfn,rid,fx,ht;
    int cnt;
    auto dfs(int u,int h=0,int f=1)->void{
        dfn[u]=++cnt;rid[dfn[u]]=u;ht[u]=h;
        hx[h].push_back(dfn[u]);fx[u]=f;
        for(auto&i:gr[u]) if(i!=f) dfs(i,h+1,u);
        rdfn[u]=cnt;
    }
    auto ask(int u,int las,int h,int delta,const int sqr,bool spc=false)->void{
        if(checkml(u)){
            auto nhx=h+(int)(sqr/1.2);
            auto lb=ranges::lower_bound(hx[nhx],dfn[u]);
            auto rb=ranges::upper_bound(hx[nhx],rdfn[u]);
            while(lb==rb){
                --nhx;spc=true;
                lb=ranges::lower_bound(hx[nhx],dfn[u]);
                rb=ranges::upper_bound(hx[nhx],rdfn[u]);
            }
            if(!spc) for(auto i=(int)(sqr/1.2+1);i<(int)(sqr*1.3);++i){
                auto nlb=ranges::lower_bound(hx[h+i],dfn[u]);
                auto nrb=ranges::upper_bound(hx[h+i],rdfn[u]);
                if(nlb==nrb) break;
                if(nrb-nlb<rb-lb) lb=nlb,rb=nrb,nhx=h+i;
            }
            if(nhx!=h){
                auto chs=false;
                const auto clb=lb;
                if(rb-lb<sqr+7) for(;lb<rb;++lb){
                    const auto ux=rid[*lb];
                    if(checkml(ux)){
                        ask(ux,u,nhx,nhx-h,sqr,spc);
                        chs=true;
                        break;
                    }
                }
                if(!chs) ask(rid[*clb],u,nhx,nhx-h,sqr,true);
            }else{
                spc=true;
            }
        }else{
            spc=true;
        }
        if(spc&&checkml(u)) throw u;
        if(!checkml(las)) return;
        checkml(u);
        auto cntx=0;
        while(checkml(las)&&cntx<delta+2) ++cntx,checkml(u);
        assert(las==1||cntx<delta+2);
        throw fx[fx[las]];
    }
public:
    auto insert(int u,int v){
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    auto play(){
        dfs(1);
        #if not defined(ONLINE_JUDGE)
            const auto sqr=3;
        #else
            const auto sqr=50;
        #endif
        try{
            ask(1,1,0,sqr,sqr);
            assert(false);
        }catch(int ans){
            answer(ans);
        }
    }
    check(int n):gr(n+307),hx(n+307),dfn(n+307),rdfn(n+307),rid(n+307),fx(n+307),ht(n+307),cnt(0){}
};
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T;cin>>T;
    while(T--) [&]{
        int n;cin>>n;check ck(n);
        cir(i,0,n-1){
            int u,v;cin>>u>>v;
            ck.insert(u,v);
        }
        ck.play();
    }();
    return 0;
}