← 返回题目列表

AtCoder · arc028_3

C. 分而治之高桥王国

中文机器翻译题面 查看原题

問題文

高桥王国是 它由 N 个城镇组成,每个城镇有 它们的编号最大为 0 它们的编号最大为 N-1 。此外,还有一条道路连接两个城镇。 N-1 有书,你可以通过多条道路从任何一个城镇到达任何一个城镇。

高桥王国的国王高桥正在决定将哪个城镇作为首都。高桥决定计算出“余额值”,作为决定资本的参考。镇 当 v 为资本时,“余额值”为 v 可以相互穿越而不经过的城镇集合的最大大小。

例如下图所示的城镇 如果 1 是首都,{town 0, 町 4} 或 {城镇 在一组城镇中,例如 2} 或 {城镇 在一组城镇中,例如 3},城镇 现在可以在不经过 1 的情况下交叉路径。其中最大的集合是 {town 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