考虑维护当前答案的候选点集 $S$，初始为整棵树。

询问一个点 $u$ 时，若返回 $1$，则令 $S \gets S \cap \operatorname{subtree}(u)$；若返回 $0$，则令 $S \gets S - \operatorname{subtree}(u)$，然后令 $S \gets \{fa_u \mid u \in S\}$。显然，$S$ 始终连通。

可以发现，操作后 $S$ 不超过 $\max(\text{siz}_u, n - \text{siz}_u)$，也就是这是一个边分治的形式。

边分治在图是菊花图的时候会被卡成 $O(n^2)$，但是此时树的深度很小。人类智慧地， 取 $u$ 为 $S$ 的根结点 $rt$ 的 $\lceil {\text{len}_{rt} \over 2} \rceil$ 级长儿子询问，发现直接过了。甚至直接把询问次数调成 $100$ 都能过（即官方题解里的 Bonus），大家有什么头绪吗？

提交记录