C - 高橋王国の分割統治 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋王国は N 個の町からなり、それぞれの町には 0 から N-1 までの番号がついています。また、２つの町を繋ぐ道が N-1 本あり、どの町からどの町へもいくつかの道を使うことで辿り着けるようになっています。

高橋王国の王様である高橋君は、首都にする町を決めようとしています。高橋君は首都を決める参考にするために「バランス値」を計算してみることにしました。町 v を首都としたときの「バランス値」は、町 v を通らずに相互に通行可能である町の集合の最大の大きさです。

例えば、下の図の町 1 を首都とした場合、{町 0, 町 4} や {町 2} や {町 3} などの町の集合において、町 1 を通らずに相互に通行することが可能となっています。そのうち最も大きい集合は {町 0, 町 4} であり、その大きさは 2 であるため、町 1 を首都としたときの「バランス値」は 2 となります。

figure

入力

入力は以下の形式で標準入力から与えられる。

N
p_1
p_2
:
p_{N-1}
  • 1 行目には、町の個数を表した整数 N (1 ≦ N ≦ 100,000) が与えられる。
  • 2 行目からの N-1 行では、道の情報が与えられる。このうち i 行目では１つの整数 p_i (0 ≦ p_i ≦ i-1) が与えられる。これは、町 i と 町 p_i を繋ぐ道があることを表す。

部分点

この問題には部分点が設定されている。

  • N ≦ 1000 を満たすテストケースすべてに正解した場合は 30 点が与えられる。

出力

N 行に出力せよ。そのうち i 行目には、町 i-1 を首都としたときの「バランス値」を表す 1 つの整数を出力せよ。

入力例1

5
0
1
1
0

出力例1

3
2
4
4
4

このケースでの入力は、問題文中の図のような道の情報を表しています。

入力例2

3
0
0

出力例2

1
2
2