CF1990E1 Catch the Mole(Easy Version)

Genius_Star · 2026-11-11 15:08:35 · 题解

来个极限 157 询问的做法，是 2(\sqrt n + \sqrt{\sqrt n}) 的。

思路：

考虑树分块，把关键点找出来，那么每个点到最近关键祖先的距离是 \sqrt n 的，且关键点点数也是 \sqrt n 的。

把所有关键点拿出来，按照深度从深到浅去询问，如果鼹鼠确实在当前关键点子树内时停止：

• 设在查询 u 的时候停止了。

• 那么根据性质，鼹鼠到 u 的距离 \le \sqrt n。

• 于是随便找一个其它的点 v 使得鼹鼠不在它子树内，这是容易找到的，显然选择 u 子树内随便一个叶子即可。

• 那么每次询问 v 的时候鼹鼠都会往上跳一次，每次查询 v 后再查询一下 u，如果不在 u 子树了，说明鼹鼠上次询问时刚好在 u 这里，就可以确定鼹鼠的位置。

但是这样你分析一下最劣是 3 \sqrt n 的，只能通过 E1，无法通过 E2。

考虑优化，每次询问 v 都看一下 u 太劣了，继续分块，考虑 \sqrt{\sqrt n} 次询问 v 后再看一下 u，如果此时 u 子树内没用鼹鼠，那么鼹鼠肯定在 u 祖先上且距离 u 不超过 \sqrt{\sqrt{n}}，于是从 u 的 \sqrt{\sqrt{n}} 级祖先开始往下查询，过程中鼹鼠不会动，找到点 v 不在了说明它之前在 fa_v，现在又跳了，就可以确认位置了。

这样显然是 2(\sqrt n + \sqrt{\sqrt n}) = 159 的，理论可以过；精细实现可以调一下中间的块长，可以做到 157！

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 5005, B1 = 71, B2 = 9;
int n, tot, tp, hd[N], to[N << 1], nx[N << 1];
int fa[N], dep[N], h[N], lf[N], st[N], vis[N];
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void add(int u, int v){
    to[++tot] = v, nx[tot] = hd[u], hd[u] = tot;
}
inline int ask(int x){
    putchar('?'), putchar(' '), write(x), putchar('\n'), fflush(stdout);
    return read();
}
inline void ans(int x){
    putchar('!'), putchar(' '), write(x), putchar('\n'), fflush(stdout);
}
inline bool cmp(int x, int y){
    return dep[x] > dep[y];
}
void dfs(int u, int p){
    fa[u] = p, dep[u] = dep[p] + 1, h[u] = 0, lf[u] = u;
    for(int i = hd[u]; i; i = nx[i]){
        int v = to[i];
        if(v == p)
            continue;
        dfs(v, u);
        lf[u] = lf[v];
        if(!vis[v])
            h[u] = max(h[u], h[v] + 1);
    }
    if(h[u] == B1 && u != 1)
        vis[u] = 1, st[++tp] = u;
}
inline void solve(){
    n = read(), tot = tp = 0;
    for(int i = 1; i <= n; ++i)
        hd[i] = vis[i] = dep[i] = 0;
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    dfs(1, 1);
    sort(st + 1, st + tp + 1, cmp);
    int u = 1;
    for(int i = 1; i <= tp; ++i)
        if(ask(st[i])){
            u = st[i];
            break;
        }
    int v = lf[u];
    if(u == 1){
        for(int i = 1; i <= h[1]; ++i)
            if(ask(v))
                return ans(v);
        return ans(1);
    }
    while(1){
        for(int i = 1; i <= B2; ++i)
            if(ask(v))
                return ans(v);
        if(!ask(u))
            break;
    }
    int x = fa[fa[u]];
    tp = 0, st[++tp] = x;
    for(int i = 1; i < B2 && x != 1; ++i)
        x = fa[x], st[++tp] = x;
    for(int i = tp - 1; i >= 1; --i)
        if(!ask(st[i]))
            return ans(fa[st[i + 1]]);
    ans(st[1]);
}
int main() {
    int T = read();
    while(T--)
        solve();
    return 0;
}