最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 消息传递

C++ 少儿编程 1284浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

H国的社会等级森严,除了国王之外,每个人均有且只有一个直接上级,当然国王没有上级。如果$A$是$B$的上级,$B$是$C$的上级,那么$A$就是$C$的上级。绝对不会出现这样的关系:$A$是$B$的上级,$B$也是$A$的上级。

最开始的时刻是$0$,你要做的就是用1单位的时间把一个消息告诉某一个人,让他们自行散布消息。在任意一个时间单位中,任何一个已经接到消息的人,都可以把消息告诉他的一个直接上级或者直接下属。

现在,你想知道:

①到底需要多长时间,消息才能传遍整个H国的所有人?

②要使消息在传递过程中消耗的时间最短,可供选择的人有哪些?

【输入】

第一行为一个整数$N$,表示H国人的总数,假如人按照$1$到$n$编上了号码,国王的编号是$1$。

第二行到第$N$行(共$N-1$行),每一行一个整数,第$i$行的整数表示编号为$i$的人直接上级的编号。

【输出】

输出共计两行:

第一行为一个整数,表示最后一个人接到消息的最早时间。

第二行有若干个数,表示可供选择人的编号,按照编号从小到大的顺序输出,中间用一个空格隔开。

【输入样例】

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≤3000$。

对于50%的数据,$N≤20000$。

对于100%的数据,$N≤200000$。

您必须 登录 才能发表评论!