CF1044B Intersecting Subtrees 做题记录

这是一道交互题。

你和 Alice 正在玩一个奇怪的游戏。给出一棵 $N$ 个点的树，双方分别给顶点编号为 $1$ 到 $N$，双方都不知道对方给树编号的方式。

接着双方在自己对应的树上选择一个联通子图，在你的编号方式对应的树上你选择了$x_1,x_2,\dots,x_{k_1}$，在 Alice 的编号方式对应的树上 Alice 选择了 $y_1,y_2,\dots,y_{k_2}$，双方都知道 $x_1,\dots,x_{k_1}$ 与 $y_1,\dots,y_{k_2}$ 的值

现在你想知道两个子图是否存在至少一个公共点。你可以进行询问，问题有以下两种：

$A,x$：得到在你的编号方式下的 $x$ 号点在Alice的编号方式下的值
$B,x$：得到在Alice的编号方式下的 $x$ 号点在你的编号方式下的值

现在请你使用不多于 $5$ 次询问得出是否存在公共点，或者确定两棵子树没有公共点。

$1\le n\le 1000$。

首先挑一个对方选了的点 $u$，询问我们对这个点的编号，设询问的结果为 $v$。

那么若 $v$ 被我们选了显然直接输出答案，否则考虑以 $v$ 为根的有根树：

显然对方选的点集若包含某个点 $q$ 那么也一定包含 $q$ 的所有祖先，那么设我们选的点集中深度最小的点为 $p$，公共点只会有两种情况：

• 没有公共点；
• $p$ 是其中一个公共点。

所以再问一下 $p$ 在对方编号方式里的编号即可。

一共用了两次询问，足以通过此题。