题目描述

巴蜀国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果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： 

81134443

输出样例#1： 

53 4 5 6 7 这道题其实不太难想到。 因为一个点每次只能把消息传给一个点。所以主要是贪心的思想，跟排队打水差不多，就是每次先把消息传给剩下需要时间最大的一个子树。 但是因为不确定根，所以需要遍历一下根，再每次搜一遍。 搜索的时候把时间存一下即可。 从所有子节点中找出时间最大的即以这个点为根所需要的时间。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 using namespace std; 7 typedef long long ll; 8 const ll maxn = 1e3+5; 9 ll read()10 {11     ll a = 0,b = 1;12     char c = getchar();13     while(c < '0' or c > '9')14     {15         if(c == '-') b = -1;16         c = getchar();17     }18     while(c >= '0' and c <= '9')19     {20         a = a * 10 + c - '0';21         c = getchar();22     }23     return a * b;24 }25 ll cmp(ll a,ll b)26 {27     return a > b;28 }29 vector
            
             v[maxn];30 ll dp[maxn],ans[maxn],minn = 0x7fffffff,n;31 void dfs(ll x, ll f)32 {33 ll b[550] = { 0},cnt = 0;34 for(int i=0; i