Catch the Mole (CF1990E2 Hard Version / Bonus) 题解

本篇题解解决了出题人提出的 100 次询问加强版（Bonus）。

题意

这是一道交互题。

给出一棵 $n$ 个点的树，一个隐藏的鼹鼠在其中一个节点。

每次你可以以 ? x 的格式询问一个节点 $x$。

• 如果返回 $0$，说明鼹鼠不在以 $x$ 为根的子树中。随后，如果鼹鼠不在根节点，那么他会往父节点移动一次。
• 如果返回 $1$，说明鼹鼠在以 $x$ 为根的子树中。

你需要定位这个鼹鼠，以 ! x 的格式回答，说明询问结束之后鼹鼠在 $x$ 节点。

Easy Version：询问次数不超过 $300$ 次。
Hard Version：询问次数不超过 $160$ 次。
Bonus：询问次数不超过 $100$ 次。

Hint

1. 如果一次询问的结果为 $0$，你可以删除这棵子树。
2. 如果询问对象是一个叶节点，当返回为 $1$ 时，答案为该节点；否则，鼹鼠将会向上移动一格。
3. 如果一棵子树的返回为 $1$，那么我们可以通过 Hint 2 把它赶出这个子树。

Hard Version 解法

（为方便描述，下面将"以 $x$ 为根的子树"简称作"子树 $x$"）

首先，如果我们已经确定了鼹鼠一定在从根节点开始的一条链上，那么通过二分查找，可以用最多 $13$ 次询问找到这只鼹鼠。

于是，问题变为用 $147$ 次询问如何将其确定在这样一条链上。

定义节点 $x$ 到根的距离为 $dep_x$，到子树 $x$ 内最深的节点的距离为 $ped_x$。

通过 Hint 3，不难想到如果我们已经确定了鼹鼠在子树 $x$ 里，那么我们可以通过 $ped_x$ 次操作将其赶出这棵子树，使其在一条满足要求的链上。

考虑每次查询一个 $x$ 使得 $ped_x = \sqrt{n}$，如果返回 $0$ 就删除子树 $x$，否则用 $\sqrt{n}$ 次将鼹鼠赶到一条满足要求的链上。如果没有这样的子树，即所有 $ped_x$ 都小于 $\sqrt{n}$，那么直接用 $\sqrt{n}$ 次使其到达根节点。

不难发现如果删除的话，每次会删除至少 $\sqrt{n}$ 个节点，所以最多只能删 $\sqrt{n}$ 次，所以询问次数最多为 $2\sqrt{n}$，不超过 $141$，足以通过 Hard Version。

Bonus 解法（100 次询问）

我们需要通过不超过 $87$ 次操作将鼹鼠赶到一条满足要求的链上。

每次，我们找一个点 $x$，使得以 $x$ 为根的子树为一条链，而且以 $x$ 的父亲为根的子树不为一条链。

这样的好处在于，如果我们确定鼹鼠在子树 $x$ 里，我们无需将其赶出这棵子树，可以直接在这个纯净链上二分。

如果鼹鼠不在这棵子树里，我们删除这棵子树和所有的叶子节点，然后重复以上操作即可。

不过，这种做法下，时间复杂度为 $O(tn^2)$，高达 $2.5\times 10^9$。于是，我们需要优化找符合要求的点 $x$ 的过程。

考虑找一个叶子节点倍增往上跳，用线段树维护子树大小来确定子树 $x$ 是否是一条链，这样最终时间复杂度为 $O(tn\log^2 n)$，足以通过本题。

代码

#include<bits/stdc++.h>
#define cint const int
#define iint inline int
#define ll long long
#define cll const long long
#define ill inline long long
using namespace std;

iint read() {
    int num = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        num = (num << 1) + (num << 3) + (ch - '0');
        ch = getchar();
    }
    return num;
}

int n;
int head[5001], f[5001][13], a[5001], deg[5001], dfn[5001], l[5001], r[5001];
struct edge { int to, nxt; } e[10000];
int tot;

struct que {
    int a[5001], h, t;
    inline void clear() { h = 0, t = -1; }
    inline void push(cint x) { a[++t] = x; }
    inline void pop() { ++h; }
    iint front() { return a[h]; }
    iint size() { return t - h + 1; }
    inline bool empty() { return t < h; }
} leaf;

bool query(cint x) {
    printf("? %d\n", x);
    fflush(stdout);
    return read();
}

inline void add_edge(cint u, cint v) {
    e[++tot] = edge{v, head[u]};
    head[u] = tot;
    e[++tot] = edge{u, head[v]};
    head[v] = tot;
}

void dfs(cint now) {
    l[now] = dfn[now] = ++tot;
    for (int i = head[now]; i; i = e[i].nxt) {
        if (e[i].to == f[now][0]) continue;
        ++deg[now];
        f[e[i].to][0] = now;
        dfs(e[i].to);
    }
    r[now] = tot;
}

inline void init() {
    for (int k = 1; k <= 12; ++k)
        for (int i = 1; i <= n; ++i)
            f[i][k] = f[f[i][k-1]][k-1];
    leaf.clear();
    for (int i = 1; i <= n; ++i)
        if (!deg[i]) leaf.push(i);
}

namespace A {
    namespace T {
        struct node { int l, r, sum; } t[20001];
        int idx[5001];

        void Build(cint p, cint l, cint r) {
            t[p].l = l; t[p].r = r;
            if (l == r) {
                t[p].sum = 1;
                idx[l] = p;
                return;
            }
            cint mid = (l + r) >> 1;
            Build(p << 1, l, mid);
            Build(p << 1 | 1, mid + 1, r);
            t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
        }

        void build() { Build(1, 1, n); }

        inline void update(cint x) {
            for (int i = idx[x]; i; i >>= 1) --t[i].sum;
        }

        int Ask(cint p, cint l, cint r) {
            if (t[p].l > r || t[p].r < l) return 0;
            if (t[p].l >= l && t[p].r <= r) return t[p].sum;
            return Ask(p << 1, l, r) + Ask(p << 1 | 1, l, r);
        }

        int ask(cint l, cint r) { return Ask(1, l, r); }
    }

    iint size(cint x) { return T::ask(l[x], r[x]); }

    iint find(int x) {
        int len = 1;
        for (int i = 12; i >= 0; --i) {
            if (f[x][i] == 0) continue;
            if (size(f[x][i]) == len + (1 << i)) {
                len += (1 << i);
                x = f[x][i];
            }
        }
        return x;
    }

    inline bool check() { return query(find(leaf.front())); }

    inline void del() {
        for (int i = leaf.front(); ; i = f[i][0]) {
            --deg[i];
            if (deg[i] > 0) break;
            T::update(dfn[i]);
        }
        leaf.pop();
        for (int i = leaf.size(); i; --i) {
            cint x = leaf.front();
            leaf.pop();
            --deg[f[x][0]];
            T::update(dfn[x]);
            if (!deg[f[x][0]]) leaf.push(f[x][0]);
        }
    }
}

namespace B {
    int find(cint l, cint r) {
        cint mid = (l + r) >> 1;
        if (l >= r) return a[mid];
        if (query(a[mid])) return find(l, mid);
        if (a[r] == 1) {
            if (mid + 1 == r) return 1;
            return find(mid + 2, r);
        }
        return find(mid + 2, r + 1);
    }

    void solve() {
        int x = leaf.front();
        tot = 0;
        while (x) {
            a[++tot] = x;
            x = f[x][0];
        }
        printf("! %d\n", find(1, tot));
        fflush(stdout);
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        head[i] = 0;
        deg[i] = 0;
    }
    tot = 0;
    for (int i = 1; i < n; ++i) add_edge(read(), read());
    tot = 0;
    dfs(1);
    init();
    A::T::build();
    while (!A::check()) A::del();
    B::solve();
}

int main() {
    int T = read();
    while (T--) solve();
    return 0;
}