CF1044B Intersecting Subtrees 做题记录

这是一道交互题。

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

接着双方在自己对应的树上选择一个联通子图,在你的编号方式对应的树上你选择了x1,x2,,xk1x_1,x_2,\dots,x_{k_1}在 Alice 的编号方式对应的树上 Alice 选择了 y1,y2,,yk2y_1,y_2,\dots,y_{k_2},双方都知道 x1,,xk1x_1,\dots,x_{k_1}y1,,yk2y_1,\dots,y_{k_2} 的值

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

A,xA,x:得到在你的编号方式下的 xx 号点在Alice的编号方式下的值
B,xB,x:得到在Alice的编号方式下的 xx 号点在你的编号方式下的值

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

1n10001\le n\le 1000

首先挑一个对方选了的点 uu,询问我们对这个点的编号,设询问的结果为 vv

那么若 vv 被我们选了显然直接输出答案,否则考虑以 vv 为根的有根树:

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

  • 没有公共点;
  • pp 是其中一个公共点。

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

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