题面
题目描述
巴蜀国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果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
题解
这题有毒！！！
数组开1000MLE？？
开2000AC了？？？
一脸懵逼。
回归正题
这道题目枚举+树形DP
建完边之后，依次枚举从哪个点开始
而当前这个节点传递给它的整棵子树的最小的时间
是它所有子节点的，最小时间加上它的子节点个数 ，再减去当前这个子节点所需的最小时间的排名，最后的最大值加1
为什么是这样？
当前节点的所有子树，遍历需要时间，而在遍历的过程中，可以传递给其他的子节点，又因为其他子节点的时间更少，因此靠后传递的总时间会更少，所以有了以上的式子。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 2001
#define rg register
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
struct Line
{
int v,next;
}e[MAX];
int h[MAX],cnt=0;
int ans=21474647,top=0;
int S[MAX];
int N;
inline void Add(rg int u,rg int v)
{
e[cnt]=(Line){v,h[u]};
h[u]=cnt++;
}
int DFS(rg int x,rg int ff)
{
rg int tot=0;
rg int f[MAX];
for(rg int i=h[x];i!=-1;i=e[i].next)//遍历所有子节点
{
if(e[i].v!=ff)//没必要传递回去
f[++tot]=DFS(e[i].v,x)+1;//每个子节点的最短时间
}
rg int re=0;
sort(&f[1],&f[tot+1]);
for(int i=tot;i;--i)
re=max(re,f[i]+tot-i);
return re;
}
int main()
{
memset(h,-1,sizeof(h));
N=read();
int v;
for(int i=2;i<=N;++i)
{
v=read();
Add(v,i);
Add(i,v);
}
//f[i]表示告诉完i的所有子树的最短时间（重新遍历一遍）
for(int i=1;i<=N;++i)//依次枚举告诉哪个人
{
v=DFS(i,i);
if(v<ans)
{
ans=v;
top=0;
}
if(v==ans)
S[++top]=i;
}
printf("%d
",ans+1);
for(int i=1;i<=top;++i)
printf("%d ",S[i]);
return 0;
}