問題文
高桥王国是 它由 N 个城镇组成,每个城镇有 它们的编号最大为 0 它们的编号最大为 N-1 。此外,还有一条道路连接两个城镇。 N-1 有书,你可以通过多条道路从任何一个城镇到达任何一个城镇。
高桥王国的国王高桥正在决定将哪个城镇作为首都。高桥决定计算出“余额值”,作为决定资本的参考。镇 当 v 为资本时,“余额值”为 v 可以相互穿越而不经过的城镇集合的最大大小。
例如下图所示的城镇 如果 1 是首都,{town 0, 町 4} 或 {城镇 在一组城镇中,例如 2} 或 {城镇 在一组城镇中,例如 3},城镇 现在可以在不经过 1 的情况下交叉路径。其中最大的集合是 {town 0, 町 4} 其大小为 2 ,所以镇 1 为资本时的“余额值”为 2 。
入力
输入是按以下格式从标准输入给出的。
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