← 返回题目列表

Codeforces · 860/E

E. 阿尔卡季和一个无名小卒

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

Arkady的话在一家大公司。有n名员工在一个严格的等级制度中工作。也就是说,除首席执行官外,每位员工都只有一名直属经理。首席执行官是所有员工的管理者(通过一系列直属管理者)。

每个员工都有一个整数等级。 CEO 的级别等于 1,其他员工的级别等于其直属经理的级别加 1。

Arkady在公司的职位很好,但他觉得自己在公司的架构中无足轻重,可以替代他的人还有很多。他介绍了可替代性的价值。考虑员工 a 和员工 b,后者是 a 的经理(不一定是直接经理)。那么a相对于b的可替代性r(a,b)就是经理b的级别不大于a级别的下属(不一定是直属)的数量。除了可替代性之外,阿尔卡迪还引入了可忽略性的价值。员工 a 的可忽略性 za 等于他相对于所有经理的可替代性之和,即 $$z_{a} = \sum_{b} r(a,b)$$,其中该总和被接管到他的所有经理 b 上。

阿尔卡迪不仅对自己的忽视感兴趣,而且对公司所有员工的忽视感兴趣。求每个员工对于Arkady 的可忽略性。

输入

第一行包含单个整数 n (1 ≤ n ≤ 5·105) — 公司的员工人数。

第二行包含 n 个整数 p1, p2, ..., pn (0 ≤ pi ≤ n),其中如果第 i 个员工是 CEO,则 pi = 0,否则 pi 等于 ID 为 i 的员工的直属经理的 ID。员工编号从 1 到 n。可以保证这些值中恰好有一个 0,并且 CEO 是所有其他员工的经理(不一定是直属经理)。

输出

打印 n 个整数 — 按 ID 顺序排列的所有员工的可忽略性:z1、z2、...、zn。

示例

输入 #1

4
0 1 2 1

输出 #1

0 2 4 2

输入 #2

5
2 3 4 5 0

输出 #2

10 6 3 1 0

输入 #3

5
0 1 1 1 3

输出 #3

0 3 3 3 5

注意

考虑第一个例子:

- CEO 没有经理,因此 z1 = 0。
- r(2, 1) = 2(员工2和4符合条件,员工3的级别太大)。因此z2 = r(2, 1) = 2。
- 同样,z4 = r(4, 1) = 2。
- r(3, 2) = 1(员工3是2的下属,具有合适的级别)。 r(3, 1) = 3(员工2、3、4符合条件)。因此z3 = r(3, 2) + r(3, 1) = 4。