P2018 消息传递

    • 515通过
    • 896提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 树形结构
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    现在,你想知道:

    1.到底需要多长时间,消息才能传遍整个巴蜀国的所有人?

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

    输入输出格式

    输入格式:

    输入文件的第一行为一个整数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
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。