题解：CF1990E2 Catch the Mole(Hard Version)

· · 题解

观察到 n=5000，操作次数是 160。

发现大致是类似于 \sqrt n 的，尝试了一下发现是 2 \sqrt n。

但是貌似还多了 18 次，我们猜测这是 \log n。

目标就是 2 \sqrt n+\log n。

什么情况下会出现 2 \sqrt n 呢？我猜测这一定是 B+\frac nB 然后均值出来的。

那么目标就是 \log n+ B + \frac nB。

我们先让鼹鼠行动 $B$ 次（方法是询问一个叶子 $B$ 次，但是如果我们运气好鼹鼠就在这个叶子上——返回了 $1$，那么直接回答这个叶子即可），这样的话我们搜索时就可以排除掉深度 $<B$ 的子树，因为鼹鼠往上爬了 B 次，不可能在这个子树上。 我们来进行 dfs。 举行了 `dfs(u)` 代表行动路径必定有 $u \to 1$。 + 如果没有深度 $\geq B$ 的子树，那么其实鼹鼠已经被你抓到了，就在 $u$ 上。 + 如果有深度 $\geq B$ 的子树，询问子树根，看返回值。如果返回值为 $1$，那么鼹鼠就在这个子树中，继续 dfs 下去。如果搜到最后返回值全部为 $0$，那么很不对劲，其实鼹鼠就在 $u$ 上！ 这个方法很深刻，但是会被链干掉，我就是卡在了这一步。 其实你询问到最后一颗子树，如果前面的都“太失望了没有”，那么其实一定在这颗子树上（虽然还可能在 $u$ 上）。 此时理性分析一下发现每次 dfs 可以干掉一个深度 $\geq B$ 的子树（至少有 $B$ 个点）所以这一部分次数是 $\frac nB$。 至此就做完了，算下来的话需要 $155$ 次操作，还留下五次，挺有意思。 代码易，不放了。