PID182 / 爱心蜗牛
题目描述

猫猫把嘴伸进池子里,正准备“吸”鱼吃,却听到门铃响了。猫猫擦了擦脸上的

水,打开门一看,那人正是她的好朋友——川川。

川川手里拿着一辆玩具汽车,对猫猫说:“这是我的新汽车!”接着,伴随一阵塑料

叩击声,玩具汽车的车门竟开了,一只蜗牛慢慢吞吞爬了出来。

“哇!这么大的蜗牛……”猫猫惊讶道。

“这是我的宠物蜗牛,他叫点点。”川川介绍道。

“把他送给我好吗?”猫猫央求道。

“可以让他陪你几天,但是不能送给你……”

点点沿着川川的身体,爬到了地上,又移到了猫猫的池子旁边,只听见猫猫向川川

介绍她的“创意吃鱼法”,心里不禁起了一丝凉意:“这个女生太毒了……吃鱼前还要玩

鱼……”转眼一看,池中的鱼依旧畅快地游来游去。

“或许这些鱼听不懂猫语吧……好在我会一点儿猫语,也会一点鱼语……阿弥陀

佛,善哉善哉。我还是救救这些鱼吧……”点点自言自语,一边费力地移动着身躯。他

认识到——单凭自己的力量,把猫猫的阴谋告诉每一条鱼,似乎不太可能——自己底盘

太低,走不快,看来只得想其他办法来传达信息。一翻认真思考之后,点点想到,如果

把猫猫的计划告诉其中一条鱼,再让鱼们互相传达消息,那么在相对较短的时间内,每

条鱼都会得知猫猫的计划。

鱼们的社会等级森严,除了国王菜鱼之外,每条鱼均有且只有一个直接上级,菜鱼

则没有上级。如果A是B的上级,B是C的上级,那么A就是C的上级。

绝对不会出现这样两条鱼A、B:A是B的上级,B也是A的上级。

最开始的时刻是0,点点要做的,就只是用1单位的时间把猫猫的阴谋告诉某一条

“信息源鱼”,让鱼们自行散布消息。在任意一个时间单位中,任何一条已经接到通知

的鱼,都可以把消息告诉他的一个直接上级或者直接下属。

现在,点点想知道:

1. 到底需要多长时间,消息才能传遍池子里的鱼?

2.使消息传递过程消耗的时间最短,可供选择的“信息源鱼”有那些?

输入格式

有多组输入数据,每组数据:

第一行有一个数N(N≤ 1000),表示池中的鱼数,池鱼按照1到n编上了号码,国

王菜鱼的标号是。1

第2行到第N行(共N-1 行),每一行一个数,第I行的数表示鱼I的直接上级的标

号。

输出格式

对于每组输入数据:

第一行有一个数,表示最后一条鱼接到通知的最早时间。

第二行有若干个数,表示可供选择的鱼F的标号,按照标号从小到大的顺序输出,

中间用空格分开。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论