A21047.消息传递
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
巴蜀国的社会等级森严,除了国王之外,每个人均有且只有一个直接上级,当然国王没有上级。如果 A 是 B 的上级,B 是 C 的上级,那么 A 就是 C 的上级。绝对不会出现这样的关系:A 是 B 的上级,B 也是 A 的上级。
最开始的时刻是 0,你要做的就是用 1 单位的时间把一个消息告诉某一个人,让他们自行散布消息。在任意一个时间单位中,任何一个已经接到消息的人,都可以把消息告诉他的一个直接上级或者直接下属。
现在,你想知道:
- 到底需要多长时间,消息才能传遍整个巴蜀国的所有人?
- 要使消息在传递过程中消耗的时间最短,可供选择的人有那些?
输入格式
输入文件的第一行为一个整数 N(N≤1000),表示巴蜀国人的总数,假如人按照 1 到 n 编上了号码,国王的编号是 1。第 2 行到第 N 行(共 N−1 行),每一行一个整数,第 i 行的整数表示编号为 i 的人直接上级的编号。
输出格式
文件输出共计两行:
- 第一行为一个整数,表示最后一个人接到消息的最早时间。
- 第二行有若干个数,表示可供选择人的编号,按照编号从小到大的顺序输出,中间用空格分开。
输入输出样例
输入#1
8 1 1 3 4 4 4 3
输出#1
5 3 4 5 6 7
说明/提示
文件输出共计两行:
- 第一行为一个整数,表示最后一个人接到消息的最早时间。
- 第二行有若干个数,表示可供选择人的编号,按照编号从小到大的顺序输出,中间用空格分开。