来自"NOCOW"

---

Solution From Xcheng:

求树的中心。 树的中心的定义就是 到（最远的点的距离）最短的点。

方法一： 预处理每二个结点间的距离 然后找中心 O(n^3) 超时

方法二： BFS twice 第一次找离结点1最远的点K 再找离K最远的点X K~X就是最长链 链上的中点就是中心 O(n)

方法三： 第一次动规做f[i]:=max(f[son])+1，第二次动规做f[i]:=max(f[i],f[father] + 1) 。 但是存在一个问题就是如果f[father]的值是从i那里得到的，这样计算显然就错了。 不要放弃，在实际操作过程中，f需要记下两个值，一个是最优值，一个是次优值，这两个值必须由不用的子结点得到。这样当最优值发生矛盾的时候，次优值一定不会矛盾。问题就解决了。复杂度O(N)十分的理想。

---

看一眼就知道是树形DP，以随便一个节点（我的程序里是1）建树。

f1[i]表示以i为根的子树中，i到叶子节点的距离最大值；

f2[i]表示以i为根的子树中，i到叶子节点的距离次大值；

同时分别记录f1[i]，f2[i]是从哪个子树更新来的

g[i]表示除了以i为根的子树中的叶子节点外，其他的叶子节点到i的最大值。

首先一遍树形Dp算出f1，f2。

设parent[v]=w

g[v]=max(f1[w],g[w])+1 当f1[w]不从v更新而来

g[v]=max(f2[w],g[w])+1 当f1[w]从v更新而来

最后输出f1和g中最大值即可。

program cao;
const
  maxn=12000;
 
type
  node=record
    v,next:longint;
  end;
 
var
  t:array[0..maxn] of node;
  head,f1,f2,g,ans,from1,from2,fa:array[0..maxn] of longint;
  a,b,c,d,e,h,i,j,k,l,n,m,p,q,total:longint;
 
procedure init;
begin
  read(n);
  for i:=2 to n do
  begin
    read(a);
    fa[i]:=a;
    inc(total);
    t[total].v:=i;
    t[total].next:=head[a];
    head[a]:=total;
  end;
end;
 
procedure update(dis,son,v:longint);
begin
  if dis>f1[v] then
  begin
    f2[v]:=f1[v];
    from2[v]:=from1[v];
    f1[v]:=dis;
    from1[v]:=son;
  end
  else
  if dis>f2[v] then
  begin
    f2[v]:=dis;
    from2[v]:=son;
  end;
end;
 
procedure search(v:longint);
var
  i:longint;
begin
  i:=head[v];
  while i<>0 do
  begin
    search(t[i].v);
    update(f1[t[i].v]+1,t[i].v,v);
    i:=t[i].next;
  end;
end;
 
procedure search2(v:longint);
var
  i:longint;
begin
  if from1[fa[v]]=v then g[v]:=f2[fa[v]]+1 else g[v]:=f1[fa[v]]+1;
  if g[fa[v]]+1>g[v] then g[v]:=g[fa[v]]+1;
  i:=head[v];
  while i<>0 do
  begin
    search2(t[i].v);
    i:=t[i].next;
  end;
end;
 
procedure main;
begin
  search(1);
  g[0]:=-1;
  f1[0]:=-1;
  f2[0]:=-1;
  search2(1);
  for i:=1 to n do
    if f1[i]>g[i] then ans[i]:=f1[i] else ans[i]:=g[i];
end;
 
procedure print;
begin
  p:=maxlongint;
  for i:=1 to n do
    if ans[i]<p then
    begin
      k:=i;
      p:=ans[i];
    end;
  for i:=1 to n do
    if ans[i]=p then write(i,‘ ‘);
  writeln;
end;
 
begin
  init;
  main;
  print;
end.

program ural1056;
const
  maxn=10000;
var
  pr,u,d1,d2,c1,cen:array[1..maxn]of word;
  n,i,min,count,t:word;
procedure submit(d,c,x:word);
  begin
    if d>d1[x] then begin
      d2[x]:=d1[x];d1[x]:=d;c1[x]:=c;
    end
    else if d>d2[x] then d2[x]:=d;
  end;
function max(a,b:word):word;
  begin
    if a>b then max:=a else max:=b;
  end;
begin
  read(n);
  for i:=2 to n do
    read(pr[i]);
 
  for i:=n downto 2 do
    submit(d1[i]+1,i,pr[i]);
 
  for i:=2 to n do begin
    if i=c1[pr[i]] then u[i]:=d2[pr[i]]+1 else u[i]:=d1[pr[i]]+1;
    if u[pr[i]]+1>u[i] then u[i]:=u[pr[i]]+1;
  end;
 
  min:=maxint;
  for i:=1 to n do begin
    t:=max(u[i],d1[i]);
    if t<min then begin min:=t;count:=0;end;
    if t=min then begin inc(count);cen[count]:=i;end;
  end;
 
  for i:=1 to count-1 do
    write(cen[i],' ');
  writeln(cen[count]);
end.