CF1990E1 Catch the Mole (Easy Version) 题解

题目简述

这是一道交互题。

给定一棵 $n$ 个节点的树，根为 $1$。有一只“鼹鼠”藏在某个节点上。
你可以进行询问 ? x（$1\le x\le n$）：

• 若鼹鼠在以 $x$ 为根的子树内，返回 $1$；
• 否则返回 $0$，并且如果鼹鼠不在根节点 $1$，它会移动到它的父节点。

你需要用最多 $300$ 次询问找出鼹鼠当前所在的节点，并以 ! x 输出答案。
$n\le 5000$，测试用例数 $t\le 100$。

题目来源：[CF1990E1][4]。

关键性质

1. 子树删除：若询问返回 $0$，说明鼹鼠一定不在 $x$ 的子树内，且该子树未来也不可能再包含鼹鼠（因为鼹鼠只会向上移动），因此可以永久删除该子树。[2][3]
2. 驱赶操作：反复询问某个鼹鼠当前不在的叶子节点，每次返回 $0$，鼹鼠就会向根移动一步。若连续进行 $t$ 次，鼹鼠会向上移动 $t$ 步。[2]
3. 路径约束：若已知鼹鼠在子树 $nd$ 内，且驱赶 $t$ 次后，鼹鼠一定位于 $nd$ 到根的链上。[2][3]

算法思想（阈值分治）

设一个阈值 $t = \left\lfloor\sqrt{n/2}\right\rfloor$。
对每个节点 $u$ 预处理：

• $depth[u]$：节点深度（根为 $0$）
• $mdep[u]$：$u$ 子树中的最大深度
• $deepest\_son[u]$：$u$ 子树中最深的叶子

算法循环执行以下过程：

情况 A：存在节点 $nd$ 满足 $mdep[nd] - depth[nd] + 1 = t$

即 $nd$ 子树中最长链的长度正好为 $t$。

1. 询问 ? nd：
   • 返回 $0$：鼹鼠不在子树 $nd$ 内 → 删除整个子树 $nd$，继续循环。
     代价 $1$，删除至少 $t$ 个节点。
   • 返回 $1$：鼹鼠就在子树 $nd$ 内！
     此时进行 $t$ 次驱赶（反复询问一个全局叶子），鼹鼠必定被赶到 $nd$ 到根的路径上。 然后在路径上二分查找：
     每次二分询问路径上某个节点 $x$。若返回 $1$，说明鼹鼠在 $x$ 子树内（二分上移）；若返回 $0$，说明鼹鼠必在其父节点方向（二分下移，并且“失败次数”计数加 $1$）。
     最终定位到答案。

情况 B：不存在满足条件的节点 $nd$

说明当前剩余树的最大深度 $< t$。
此时直接进行 $t$ 次驱赶，鼹鼠必然到达根到全局最深叶子的路径上。
同样二分路径找到答案。

复杂度分析

• 情况 A-1（删除子树）：最多 $\frac{n}{t}$ 次操作，每次删除至少 $t$ 个节点。
• 情况 A-2（驱赶 $+$ 二分）：$t$ 次驱赶 $+$ $\log n$ 次二分。
• 情况 B：至多 $t$ 次驱赶 $+$ $\log n$ 次二分。

总操作次数 $\le \frac{n}{t} + t + 2\log n$。
取 $t = \sqrt{n/2}$ 时，$\frac{n}{t} + t \approx 2\sqrt{2n} \le 200$，加上 $\log n$ 远小于 $300$。
（$n=5000$ 时，$\sqrt{2500}=50$，操作数 $\le 50+100+13=163$）

所以该算法严格满足 Easy Version 的 $300$ 次限制 [2][3]。

代码实现（完全非递归，避免栈溢出）

以下代码使用迭代栈替代递归 DFS，消除长链时可能出现的栈溢出问题。

#include <bits/stdc++.h>
using namespace std;

int ask(int x) {
    cout << "? " << x << endl;
    int res; cin >> res;
    return res;
}

void found(int x) {
    cout << "! " << x << endl;
}

void solve() {
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // ---------- 非递归 DFS 计算 parent, depth, mdep, deepest_son ----------
    vector<int> parent(n + 1), depth(n + 1);
    vector<int> mdep(n + 1), deepest_son(n + 1);
    iota(deepest_son.begin(), deepest_son.end(), 0);

    // 第一次 DFS（前序）用栈获取遍历顺序
    stack<int> stk;
    stk.push(1);
    parent[<sup data-citation='{&quot;id&quot;:1,&quot;url&quot;:&quot;https://www.luogu.com.cn/article/a7p319rx&quot;,&quot;title&quot;:&quot;题解：CF1990E1 Catch the Mole(Easy Version)&quot;,&quot;content&quot;:&quot;ETOleader · 2024-07-21 11:30:49 · 题解 题目大意 给定一颗有 n 个节点的有根树，有一只鼹鼠在某一个节点。 每次可以进行一种询问 ? u，交互库会返回鼹鼠是不是在 u 的子树内，如果是就返回 1，否则返回 0。 同时如果询问时鼹鼠不在根且交互库返回了 0，鼹鼠会移动到父节点。 你有 300 次询问的机会，需要得到鼹鼠当前所在的节点。 题目解析 这是一种与官方题解不&quot;}'>1</sup>](https://www.luogu.com.cn/article/a7p319rx) = 0;
    depth[<sup data-citation='{&quot;id&quot;:1,&quot;url&quot;:&quot;https://www.luogu.com.cn/article/a7p319rx&quot;,&quot;title&quot;:&quot;题解：CF1990E1 Catch the Mole(Easy Version)&quot;,&quot;content&quot;:&quot;ETOleader · 2024-07-21 11:30:49 · 题解 题目大意 给定一颗有 n 个节点的有根树，有一只鼹鼠在某一个节点。 每次可以进行一种询问 ? u，交互库会返回鼹鼠是不是在 u 的子树内，如果是就返回 1，否则返回 0。 同时如果询问时鼹鼠不在根且交互库返回了 0，鼹鼠会移动到父节点。 你有 300 次询问的机会，需要得到鼹鼠当前所在的节点。 题目解析 这是一种与官方题解不&quot;}'>1</sup>](https://www.luogu.com.cn/article/a7p319rx) = 0;
    vector<int> order;  // 前序遍历序列
    while (!stk.empty()) {
        int u = stk.top(); stk.pop();
        order.push_back(u);
        for (int v : g[u]) {
            if (v != parent[u]) {
                parent[v] = u;
                depth[v] = depth[u] + 1;
                stk.push(v);
            }
        }
    }

    // 后序回溯：由底向上推 mdep 和 deepest_son
    mdep = depth;                    // 初始：自己的深度
    for (int i = order.size() - 1; i > 0; i--) {
        int u = order[i];
        int p = parent[u];
        if (mdep[u] > mdep[p]) {
            mdep[p] = mdep[u];
            deepest_son[p] = deepest_son[u];
        }
    }

    int driver_leaf = deepest_son[<sup data-citation='{&quot;id&quot;:1,&quot;url&quot;:&quot;https://www.luogu.com.cn/article/a7p319rx&quot;,&quot;title&quot;:&quot;题解：CF1990E1 Catch the Mole(Easy Version)&quot;,&quot;content&quot;:&quot;ETOleader · 2024-07-21 11:30:49 · 题解 题目大意 给定一颗有 n 个节点的有根树，有一只鼹鼠在某一个节点。 每次可以进行一种询问 ? u，交互库会返回鼹鼠是不是在 u 的子树内，如果是就返回 1，否则返回 0。 同时如果询问时鼹鼠不在根且交互库返回了 0，鼹鼠会移动到父节点。 你有 300 次询问的机会，需要得到鼹鼠当前所在的节点。 题目解析 这是一种与官方题解不&quot;}'>1</sup>](https://www.luogu.com.cn/article/a7p319rx); // 全局最深的叶子，用于驱赶

    // ---------- 阈值 t ----------
    int t = max(1, (int)sqrt(n / 2.0));
    t = min(t, n);

    vector<int> deleted(n + 1, 0);   // 标记已删除的子树

    // ---------- 主循环 ----------
    while (true) {
        // 寻找符合条件的节点 nd
        int nd = 0;
        for (int i = 1; i <= n; i++) {
            if (!deleted[i] && mdep[i] - depth[i] + 1 == t) {
                nd = i;
                break;
            }
        }

        if (nd != 0) {
            // 情况 A
            int res = ask(nd);
            if (res == 0) {
                // 删除子树 nd（用栈实现 BFS/DFS，避免递归）
                stack<int> del_stk;
                del_stk.push(nd);
                while (!del_stk.empty()) {
                    int u = del_stk.top(); del_stk.pop();
                    if (deleted[u]) continue;
                    deleted[u] = 1;
                    for (int v : g[u]) {
                        if (v != parent[u] && !deleted[v])
                            del_stk.push(v);
                    }
                }
                continue;
            } else {
                // 驱赶 t 次
                for (int i = 0; i < t; i++) ask(driver_leaf);

                // 构造 nd 到根的路径
                vector<int> path;
                for (int cur = nd; cur != 0; cur = parent[cur])
                    path.push_back(cur);
                reverse(path.begin(), path.end());

                // 二分查找
                int lo = 0, hi = (int)path.size() - 1;
                while (lo < hi) {
                    int mid = (lo + hi + 1) >> 1;
                    int x = path[mid];
                    if (ask(x)) lo = mid;
                    else hi = mid - 1;
                }
                found(path[lo]);
                return;
            }
        } else {
            // 情况 B：剩余树深度小于 t
            for (int i = 0; i < t; i++) ask(driver_leaf);

            vector<int> path;
            for (int cur = driver_leaf; cur != 0; cur = parent[cur])
                path.push_back(cur);
            reverse(path.begin(), path.end());

            int lo = 0, hi = (int)path.size() - 1;
            while (lo < hi) {
                int mid = (lo + hi + 1) >> 1;
                int x = path[mid];
                if (ask(x)) lo = mid;
                else hi = mid - 1;
            }
            found(path[lo]);
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}