3741. 构树挑战

单点时限: 1.0 sec

内存限制: 512 MB

Cuber QQ 深陷于二叉树的美好而无法自拔。

他最近在研究一个问题,系统给定一棵有根二叉树(默认 $1$ 为根结点)和一个目标结点,Cuber QQ 每次可以询问一个结点,系统会反馈是否为目标结点的祖先,如果是会返回 Yes ,否则返回 No。现在系统允许 Cuber QQ 给出若干次询问,之后确定目标结点所在位置。 Cuber QQ 希望询问次数越少越好。

Cuber QQ 马上制定了一种策略: 每次会选择结点 $u = \arg \max_{u \in V}(\min(\text{size}(u), n - \text{size}(u)))$ ,其中 $\text{size}$ 为以 $u$ 为根结点的子树大小(结点个数)。如果有多个满足要求的点,Cuber QQ 会选择其中编号小的结点。

这样每次可以排除一部分的结点。当回答是 No 的时候,可以将以$u$为根结点的子树全部排除;当回答是 Yes 的时候,可以直接将非这棵子树的结点全部排除。Cuber QQ 会更新排除结点后的新的树,并进行下一轮问题。直到最后只剩下一个点时,交互结束(当已经能够确定最后一个点位置的情况下, Cuber QQ 不会再给出任何询问)。即使最后一次回答是 No,如果目标结点唯一确定,Cuber QQ 也不会再次给出询问。

给一个简化版的题意:可以理解成给出一棵默认以 $1$ 为根结点的二叉树以及一个目标结点,Cuber QQ 每次会选择一条边使得可以将树分为尽可能相等两部分并切去不含目标结点的那一部分(如果相同选择编号小的那个结点的父边),最终只剩一个结点时停止。

现在系统为了对抗 Cuber QQ ,需要构造一个至多 $65535$ 个结点的二叉树以及目标结点,使得 Cuber QQ 的这个策略无法在 $20$ 次以内确定目标结点(恰好询问 $20$ 次确定也是不被允许的)。

例如,当你的输入是一个 $16$ 层的满二叉树的时候(一共 $65535$ 个结点),无论你如何设定目标结点,最多的询问次数是 $18$ 次。

输入格式

没有任何输入文件。

输出格式

输出你可以通过各种形式给出,可以通过提交程序代码,我们将以程序代码的输出作为评判。

你也可以直接提交 Text 文本作为输出,如果 Text 提交时显示文本长度过长(EOJ 对提交的文本长度做了限制),请选择合适的代码输出等方式解决。

输出文件第一行包含两个整数 $n(1\le n\le 65535)$ 和 $k(1\le k\le n)$ ,分别表示你构造的树的结点数量和目标结点的标号。

接下来 $n-1$ 行,每行两个整数表示树上的一条边。

你需要保证输入的树是二叉树,且根结点的编号为 $1$

样例

Input
sample
Output
7 6
1 2
1 3
2 4
2 5
3 6
3 7

提示

样例解释

第一次会问 $2$ 号结点,因为 $\text{min}(\text{size}(2), n - \text{size}(2)) = 3$ 为最大值,虽然 $3$ 号结点的值也是 $3$ ,但是编号比 $2$ 号结点大,所以会问 $2$ 号结点。这时候 $4, 5, 6, 7$ 结点的值均为 $1$ , $1$ 的值为 $0$ 。

这时会得到 No 的反馈,因此 $2, 4, 5$ 这三个结点不可能为目标结点会被 Cuber QQ 排除。余下的树只剩 $1, 3, 6, 7$ 四个结点。

第二次会问 $3$ 号结点,理由同上,这时得到 Yes 的反馈会排除 $1$ 号结点。

第三次会问 $6$ 号结点,此时得到 Yes 的反馈会排除 $3, 7$ 号结点。此时只剩下一个 $6$ 号结点,Cuber QQ 确定目标结点为 $6$ 。

这时一共问了三次问题。

Checker

为了方便你测试,我们提供三个不同操作系统下的可执行文件。

其中,你的输出应该在 in.txt 中,运行可执行文件后,Cuber QQ 在他策略下确定目标结点所需要的次数会呈现在 result.txt 中。

6 人解决,10 人已尝试。

6 份提交通过,共有 24 份提交。

7.4 EMB 奖励。

创建: 7 月前.

修改: 7 月前.

最后提交: 4 周前.

来源: EOJ Monthly 2020.1

题目标签