消息传递
题面
题目描述
巴蜀国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果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
样例输入 #1
8
1
1
3
4
4
4
3
样例输出 #1
5
3 4 5 6 7
题解
题意简述：给定一棵树，其中1是树根，要找到一个点将其染色，耗费1的时间，然后在每一个时间内，所有被染色点可以在与其相连的点中选择一个染色，将整棵树都被染完的时间即为这个点的答案。要求出最小的答案，并且指出哪些点的答案最优。
对于此类问题，我们先来思考如果指定了一个点如何求出答案。
首先明确，由于一个点可以向上向下传递，那么此时谁是父亲谁是儿子不重要了，我们只需要知道与这个点连边的点可以被这个点染色即可，那么我们可以将这个点变为树根，显然此时只能向下传递，此时这个问题就很像一个树形DP了，具体的，设\(f[x]\)表示将\(x\)染色后染完整个\(x\)的子树的最小时间（为了方便计算，这里没有将选择\(x\)的“1”计入，当然最后将答案加一即可）。那么参考这个中关于贪心的证明部分，容易知道：
\[f[x]=\max_{y\in son(x)}\lbrace f[y]+Rank_{y}\rbrace \]其中\(son(x)\)代表\(x\)的子节点集合，\(Rank_y\)是指在\(x\)的所有儿子节点中\(f\)值的排名(从大到小)。\(O(n\log_2 n)\)DP即可求解，这个上界很松，故其实\(O(n^2\log_2n)\)的枚举即可AC。
但显然，进行\(n\)次DP肯定有优化的空间。考虑二次扫描与换根法，请看这图：
对于这部分的计算，可以设\(g[x]\)表示在\(father(x)\)为根的树(整棵树)中，除了以\(x\)为根的子树的答案，对于这个的计算，可以类比\(f\)，也很简单：
\[g[x]=\max\lbrace g[fa(x)]+Rank_{fa(x)},\max_{y\in son(x)}\lbrace f[y]+Rank_y\rbrace\rbrace \]其中\(fa\)表示父节点，\(Rank\)表示将所有的\(f[y](y\in son(x))\)与\(g[fa(x)]\)放在一起从大到小排序后的排名。
有了\(g\)，\(ans[x]\)也就呼之欲出了：
\[ans[x]=1+\max\lbrace g[x]+Rank_x,\max_{y\in son(x)}\lbrace f[y]+Rank_y\rbrace\rbrace \]\(Rank\)含义类似。
进行两次DP即可求出解，需要注意的是，对于根节点\(1\)，不存在\(g\)，也不计入子节点统计\(g\)的\(g[fa(x)]\)。
加一的原因是无论是\(f[x],g[x]\)都是默认\(x\)已染色，但实际上需要1的时间将其染色。
#define N 2005
int head[N],nxt[N],ver[N],tot=1,f[N],g[N],ans[N],b[N],lst[N],n;
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dfs1(int u,int fa){
int cnt=0;
lst[u]=fa;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
dfs1(v,u);
}
for(int i=head[u];i;i=nxt[i]){
if(ver[i]==fa)continue;
b[++cnt]=f[ver[i]];
}
sort(b+1,b+cnt+1);
reverse(b+1,b+cnt+1);
for(int i=1;i<=cnt;i++){
f[u]=max(f[u],b[i]+i);
}
}
void dfs2(int u,int fa){
int cnt=0;
if(fa!=1)b[++cnt]=g[fa];
for(int i=head[fa];i;i=nxt[i]){
int v=ver[i];
if(v==u||v==lst[fa])continue;
b[++cnt]=f[v];
}
sort(b+1,b+cnt+1);
reverse(b+1,b+cnt+1);
for(int i=1;i<=cnt;i++){
g[u]=max(g[u],b[i]+i);
}
cnt=1;b[1]=g[u];
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
b[++cnt]=f[v];
}
sort(b+1,b+cnt+1);
reverse(b+1,b+cnt+1);
for(int i=1;i<=cnt;i++){
ans[u]=max(ans[u],b[i]+i);
}
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
dfs2(v,u);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=2;i<=n;i++){
int v;
cin>>v;
add(i,v);add(v,i);
}
dfs1(1,0);
ans[1]=f[1];
for(int i=head[1];i;i=nxt[i]){
int v=ver[i];
dfs2(v,1);
}
int Ans=0x3f3f3f3f;
for(int i=1;i<=n;i++)Ans=min(Ans,++ans[i]);
cout<<Ans<<endl;
for(int i=1;i<=n;i++)if(ans[i]==Ans)cout<<i<<" ";
}