CF860E.Arkady and a Nobody-men

Arkady 在一家大型公司工作。公司中共有 $n$ 名员工，遵循严格的层级管理制度。具体来说，除了 CEO 以外，每位员工都有唯一的直属上级。CEO 通过一系列直属上级关系，是所有员工的上级。

每位员工有一个整数职位等级。CEO 的等级为 $1$，其他每个员工的等级等于其直属上级的等级加 $1$。

虽然 Arkady 的职位不错，但他感觉在公司结构中自己毫不起眼，并且有很多人可以替代自己。于是他引入了“可替代性”这个概念。设有员工 $a$ 及其上级 $b$（$b$ 不是 $a$ 必须的直属上级，只要是上级即可），则员工 $a$ 关于上级 $b$ 的可替代性 $r(a, b)$ 定义为：在上级 $b$ 的所有下属（不限于直属下属）中，职位等级不高于 $a$ 的人数。

除了可替代性，Arkady 还引入了“可忽略性”这个指标。员工 $a$ 的可忽略性 $z_a$ 定义为其对所有上级的可替代性之和，即

$$z_a = \sum_{b} r(a, b)$$

其中求和对象 $b$ 为 $a$ 的所有上级。

Arkady 不仅对自己的可忽略性感兴趣，也想知道公司中每位员工的可忽略性。请计算公司中每位员工的可忽略性。

第一行一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$），表示公司员工总数。

第二行输入 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$0 \leq p_i \leq n$），其中 $p_i = 0$ 表示第 $i$ 个员工为 CEO，否则 $p_i$ 表示第 $i$ 个员工的直属上级编号。员工编号为 $1$ 到 $n$。保证 $p$ 数组中恰有一个 $0$，并且 CEO 是所有其他员工的上级（不一定是直属上级）。

输出 $n$ 个整数，按员工编号顺序依次输出他们的可忽略性：$z_1, z_2, \ldots, z_n$。

以第一个示例为例：

• CEO 没有上级，因此 $z_1=0$。
• $r(2,1)=2$（满足条件的有员工 $2$ 和 $4$，员工 $3$ 的等级过高）。所以 $z_2 = r(2,1) = 2$。
• 同理，$z_4 = r(4,1) = 2$。
• $r(3,2)=1$（员工 $3$ 是 $2$ 的下属，且等级满足条件）。$r(3,1)=3$（满足的有员工 $2$、$3$、$4$）。所以 $z_3 = r(3,2) + r(3,1) = 4$。

由 ChatGPT 5 翻译