/ Vijos / 题库 /

病毒传递

病毒传递

背景

突然眼前一阵慌乱,所有的细菌都呈现出惊慌的样子。嘟嘟一问才知道,原来是垂涎已久的小毒物向菌国发起进攻了。

描述

小毒物想要让微生物世界里的所有细菌都感染上病毒。

微生物世界的等级观念很强,除了菌王外,每个细菌均有且只有一个直接的母体,菌王则没有母体。

如果细菌a是细菌b的母体,细菌b是细菌c的母体,则细菌a就是细菌c的母体。绝不会出现这样两个细菌a、b:细菌a是细菌b的母体,细菌b是细菌a的母体。

最开始的时刻为0,小毒物要做的就是用1个单位时间把病毒传递给某一个“病毒源细菌”,然后让细菌们自行传递。在任意一个单位时间中,任何一个已经被感染的细菌,都可以将病毒传递给它的一个直接母体或直接的下一个细菌。

现在,小毒物想知道的是:
1.最少需要多长时间,所有的细菌都会感染上病毒;
2.使感染时间最短时,可供选择的“病毒源细菌”有哪些。

格式

输入格式

第一行一个数N。表示全部的细菌数。并且从1到N编上号,毒王为1。

第二行到第N行(共N-1行),每行一个数。第I行的数表示细菌I的直接母体的编号。

输出格式

第一行一个数。表示最后一个细菌被感染后的最早时间。

第二行若干个数。表示可供选择的“病毒源细菌”的编号。

样例1

样例输入1

8
1
1
1
2
2
3
7

样例输出1

5
1 2 3

限制

各个测试点1s

提示

对于 50% 的测试数据,N<=100
对于 100% 的测试数据,N<=1000

信息

ID
1688
难度
4
分类
动态规划 | 树形DP 点击显示
标签
递交数
402
已通过
183
通过率
46%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

微观世界奇遇记模拟赛