这是一道交互题。
你和 Alice 正在玩一个奇怪的游戏。给出一棵 个点的树,双方分别给顶点编号为 到 ,双方都不知道对方给树编号的方式。
接着双方在自己对应的树上选择一个联通子图,在你的编号方式对应的树上你选择了,在 Alice 的编号方式对应的树上 Alice 选择了 ,双方都知道 与 的值
现在你想知道两个子图是否存在至少一个公共点。你可以进行询问,问题有以下两种:
:得到在你的编号方式下的 号点在Alice的编号方式下的值
:得到在Alice的编号方式下的 号点在你的编号方式下的值现在请你使用不多于 次询问得出是否存在公共点,或者确定两棵子树没有公共点。
。
首先挑一个对方选了的点 ,询问我们对这个点的编号,设询问的结果为 。
那么若 被我们选了显然直接输出答案,否则考虑以 为根的有根树:

显然对方选的点集若包含某个点 那么也一定包含 的所有祖先,那么设我们选的点集中深度最小的点为 ,公共点只会有两种情况:
- 没有公共点;
- 是其中一个公共点。
所以再问一下 在对方编号方式里的编号即可。
一共用了两次询问,足以通过此题。