QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Interactive

# 5404. 述树术

统计

这是一道交互题。

出题人有一棵大小为 $N$ 的有根二叉树(每个点只有不超过两个儿子)。节点的编号为 $1 \sim N$。

注意你并不知道这一棵树的根节点,也不知道这一棵树的具体形态。你只知道树上的节点个数 $N$。

定义树上一个点集 $S$ 的虚树点集 $V = \{\operatorname{LCA} (u, v) \mid u,v \in S \}$,其中 $\operatorname{LCA}(x, y)$ 表示 $x, y$ 在树上的最近公共祖先(这里我们定义 $\operatorname LCA(x, x) = x$)。

你想要知道这一棵树的结构,于是慷慨的出题人给了你一个交互库。这个交互库会回答你的若干次询问,每次询问你可以给定一些点的标号(不能重复),交互库会返回这些点构成点集的虚树点集的大小。

交互库的询问次数是有限的,你需要在有限的询问中确定这一棵树的形态。当然,有可能出题人只讲 6-1,那一棵二叉树无法通过任意的有限次询问问出树的结构。这个时候你需 要向交互库说明不可能通过这种询问方式确定树的形态。

请不要试图攻击交互库,否则你的得分会被手动修改为 $0$ 分。

交互方式

你不需要,也不应该实现主函数,你只需要实现函数 Solve(N),并且请包含一个头文件 tree.h。这里的 $N$ 表示这一棵树的节点个数。你可以通过调用下面两个函数与交互库进行交互:

  1. Query(S)
    • 这个函数可以向交互库询问点集 $S$ 所形成的虚树节点个数。
    • 你需要保证 $S$ 中元素互不相同,且值均在 $1 \sim n$之间。交互库会返回点集 $S$ 所形成的虚树节点个数。
  2. Report(x, y)
    • 这个函数可以向交互库报告一条你发现的树边。这条边的父节点为 $x$,儿子节点为 $y$。
    • 如果这棵树的形态不可被确定,此时 $x = -1$ 且 $y = -1$。交互库会判断这棵树是否不可确定之后直接退出程序。

你需要保证报告发现所有树边均合法,且每一次报告的树边互不相同。

这个函数没有返回值。

评测时,交互库会恰好调用solve 一次。

本题保证所使用的图在交互开始之前已经完全确定,不会根据和你的程序的交互过程动态构造,因此题目中的交互操作都是确定的,你不需要关心这些操作在交互库中的具体实现。

数据保证在调用次数限制下,交互库运行所需的时间不超过 1.5s;交互库使用的内存大小固定,且不超过 128 MB。

子任务

  • 测试包1(50分):$2 \leq N \leq 500$, $N$ 为奇数。
  • 测试包2(50分):$2 \leq N \leq 1\,000$,$N$ 为偶数或者 $N >500$。

对于测试包 1,额外满足出题人给定的树上的每一个节点恰好有 $0$ 或者 $2$ 个儿子节点。

注意,选手可以通过给定的 $N$ 的奇偶性和 $N$ 的大小判断其属于哪一个测试点。

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。

基于条件基础,在一个测试点中,你的程序被判定为正确的程序,当且仅当:

  1. 你的程序所有的函数调用均合法,且在测试包 $1$ 中,Query 调用的次数不超过 $M_1 = 250\, 000$;在测试包 $2$ 中,Query 调用的次数不超过 $M_2=100\,000$。
  2. 你的程序返回了正确的结果,也就是说:
    1. 如果这棵树不能通过有限次询问确定形态,此时你的程序必须调用恰好一次 Report(x, y) 且 $x = -1, y = -1$。
    2. 如果这棵树可以通过有限次询问确定形态,此时你的程序必须调用恰好 $n-1$ 次 Report(x, y) 且每一次报告了一条不同的正确的树边。

如果选手程序被判定不是正确的,则该测试点选手得到 $0$ 分,否则交互库将会根据选手程序的交互次数给分。假设选手的程序调用了 $x$ 次 Query 操作,对于测试包 1、2,选手的得分分别为:

测试包 $1$:$\displaystyle\left\lfloor \frac{50}{\log_2 \left(1 + \frac{\max\{4500, x\}}{4500}\right)} \right\rfloor$

测试包 $2$:$\displaystyle\left\lfloor \frac{50}{\log_2 \left(1 + \frac{\max\{10500, x\}}{10500}\right)} \right\rfloor$

一个测试包的得分为这个测试包内所有测试点的得分的最低值,而选手在本题的得分为两个测试包得分之和。

数据保证总存在一种交互方式,使得其能够在 $M = \min\{M_1, M_2\} = 100\,000$ 次询问内唯一确定树的形态,或者确定在有限次内无法判断这一棵树的形态。同时保证存在一个标准算法,使得对于两个测试包其都可以获得 $50$ 分的分数。

本机测试

在附加文件(下载)中给出了 tree.cpp,这是本题的一个参考实现,选手可以在这一份代码的基础上编写自己的代码,也可以自己重新编写一份。下发的这一份代码不保证可以通过所有的测试点。 假设选手程序为 tree.cpp,使用命令 g++ -static tree.cpp grader.cpp -o tree -O2 -std=c++11 即可得到可执行文件 tree

可执行文件将从标准输入读入以下格式的数据:

  1. 第一行两个整数 $N, M$,表示树的大小和限制询问次数。
  2. 第 $2$ 到 $N+1$ 行每行两个整数,第 $i$ 行表示标号为在 $i-1$ 的点的两个儿子。如果儿子个数小于两个,缺失的部分用 $0$ 代替。
  3. 最后一行一个整数 $0$ 或 $1$,表示是否有唯一解(无为 $0$,有为 $1$)

读人完成之后,交互库将调用恰好一次函数 Solve(N),并且用输入的数据测试你的函数。你的函数正确返回后,交互库会判断你的计算是否正确,若正确则会输出 OK, Accepted! 和交互函数调用次数相关信息,否则会输出相应的错误信息。

样例

一个可能的样例输入数据为:

3 250000
2 3
0 0
0 0
1

在这个数据中一个可能的正确的过程如下:

交互操作 注释 返回值
Solve(3) 开始交互过程
Query({1,2}) 向交互库询问节点集合 $\{1, 2\}$ 组成的虚树节点个数 $2$
Query({1,3}) 向交互库询问节点集合 $\{1, 3\}$ 组成的虚树节点个数 $2$
Query({2,3}) 向交互库询问节点集合 $\{2, 3\}$ 组成的虚树节点个数 $3$
Report(1,2) 向交互库返回树上的一条边 $(1, 2)$
Report(1,3) 向交互库返回树上的一条边 $(1, 3)$

这个交互过程总共调用了 $3$ 次 Query,并且返回了正确的答案。