AT_arc028_3 [ARC028C] 高橋王国の分割統治

高桥王国由 $N$ 个城镇组成，每个城镇编号从 $0$ 到 $N-1$。另外，有 $N-1$ 条道路连接这些城镇，保证任意两个城镇之间都可以通过若干条道路互相到达。 高桥王国的国王高桥君正在决定哪个城镇作为首都。为了参考，他决定计算每个城镇作为首都时的“平衡值”。当选择城镇 $v$ 作为首都时，其“平衡值”定义为：在不经过城镇 $v$ 的情况下，能够互相到达的城镇集合中，最大集合的大小。 例如，下图中当选择城镇 $1$ 作为首都时，{城镇 $0$, 城镇 $4$}、{城镇 $2$}、{城镇 $3$} 等集合都可以在不经过城镇 $1$ 的情况下互相到达。其中最大集合为 {城镇 $0$, 城镇 $4$}，其大小为 $2$，因此城镇 $1$ 作为首都时的“平衡值”为 $2$。 

输入通过标准输入给出，格式如下： > $N$ > $p_1$ > $p_2$ > $\vdots$ > $p_{N-1}$ - 第 $1$ 行为一个整数 $N\ (1 \leq N \leq 100,\!000)$，表示城镇的数量。 - 接下来的 $N-1$ 行，每行一个整数 $p_i\ (0 \leq p_i \leq i-1)$，表示存在一条道路连接城镇 $i$ 和城镇 $p_i$。

输出共 $N$ 行。第 $i$ 行输出一个整数，表示选择城镇 $i-1$ 作为首都时的“平衡值”。

## 部分分 本题设有部分分。 - 若能通过所有 $N \leq 1000$ 的测试点，将获得 $30$ 分。 ## 样例解释 1 本样例的输入对应于题目描述中的示意图。 由 ChatGPT 4.1 翻译