题目 1773

消息传递

查看题解 ↗GitHub ↗如何评测
题号
1773
时间限制
1000 ms
内存限制
256 MB
标签
动态规划
来源
信息学奥赛一本通 · 高手训练篇·五、动态规划(高手训练)

【题目描述】

H国的社会等级森严,除了国王之外,每个人均有且只有一个直接上级,当然国王没有上级。如果AA是BB的上级,BB是CC的上级,那么AA就是CC的上级。绝对不会出现这样的关系:AA是BB的上级,BB也是AA的上级。 最开始的时刻是00,你要做的就是用1单位的时间把一个消息告诉某一个人,让他们自行散布消息。在任意一个时间单位中,任何一个已经接到消息的人,都可以把消息告诉他的一个直接上级或者直接下属。 现在,你想知道: ①到底需要多长时间,消息才能传遍整个H国的所有人? ②要使消息在传递过程中消耗的时间最短,可供选择的人有哪些?

【输入】

第一行为一个整数NN,表示H国人的总数,假如人按照11到nn编上了号码,国王的编号是11。 第二行到第NN行(共N−1N-1行),每一行一个整数,第ii行的整数表示编号为ii的人直接上级的编号。

【输出】

输出共计两行: 第一行为一个整数,表示最后一个人接到消息的最早时间。 第二行有若干个数,表示可供选择人的编号,按照编号从小到大的顺序输出,中间用一个空格隔开。

【输入样例】

文本
4
1
1
1

【输出样例】

文本
4
1 2 3 4

【提示】

【输入样例2】

文本
8
1
1
3
4
4
4
3

【输出样例2】

文本
5
3 4 5 6 7

【数据规模与约定】 对于20%的数据,N≤3000N≤3000。 对于50%的数据,N≤20000N≤20000。 对于100%的数据,N≤200000N≤200000。

文本
8\n1\n1\n3\n4\n4\n4\n3
文本
5\n3 4 5 6 7

数据下载

题目 1773 的公开数据

正在读取文件列表…

常用命令

题目 1773 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。