English · Original
Chinese · Translation
Formal · Original
Arkady words in a large company. There are _n_ employees working in a system of a strict hierarchy. Namely, each employee, with an exception of the CEO, has exactly one immediate manager. The CEO is a manager (through a chain of immediate managers) of all employees.
Each employee has an integer rank. The CEO has rank equal to 1, each other employee has rank equal to the rank of his immediate manager plus 1.
Arkady has a good post in the company, however, he feels that he is nobody in the company's structure, and there are a lot of people who can replace him. He introduced the value of _replaceability_. Consider an employee _a_ and an employee _b_, the latter being manager of _a_ (not necessarily immediate). Then the replaceability _r_(_a_, _b_) of _a_ with respect to _b_ is the number of subordinates (not necessarily immediate) of the manager _b_, whose rank is not greater than the rank of _a_. Apart from replaceability, Arkady introduced the value of _negligibility_. The negligibility _z__a_ of employee _a_ equals the sum of his replaceabilities with respect to all his managers, i.e. , where the sum is taken over all his managers _b_.
Arkady is interested not only in negligibility of himself, but also in negligibility of all employees in the company. Find the negligibility of each employee for Arkady.
## Input
The first line contains single integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of employees in the company.
The second line contains _n_ integers _p_1, _p_2, ..., _p__n_ (0 ≤ _p__i_ ≤ _n_), where _p__i_ = 0 if the _i_\-th employee is the CEO, otherwise _p__i_ equals the id of the immediate manager of the employee with id _i_. The employees are numbered from 1 to _n_. It is guaranteed that there is exactly one 0 among these values, and also that the CEO is a manager (not necessarily immediate) for all the other employees.
## Output
Print _n_ integers — the negligibilities of all employees in the order of their ids: _z_1, _z_2, ..., _z__n_.
[samples]
## Note
Consider the first example:
* The CEO has no managers, thus _z_1 = 0.
* _r_(2, 1) = 2 (employees 2 and 4 suit the conditions, employee 3 has too large rank). Thus _z_2 = _r_(2, 1) = 2.
* Similarly, _z_4 = _r_(4, 1) = 2.
* _r_(3, 2) = 1 (employee 3 is a subordinate of 2 and has suitable rank). _r_(3, 1) = 3 (employees 2, 3, 4 suit the conditions). Thus _z_3 = _r_(3, 2) + _r_(3, 1) = 4.
Arkady 在一家大型公司工作。公司中有 #cf_span[n] 名员工，采用严格的层级结构：除 CEO 外，每位员工恰好有一位直接上级。CEO 是所有员工的上级（通过直接上级的链式关系）。
每位员工有一个整数等级。CEO 的等级为 #cf_span[1]，其他每位员工的等级等于其直接上级的等级加 #cf_span[1]。
Arkady 在公司中职位不错，但他感到自己在公司结构中无足轻重，有许多人可以取代他。他引入了 _可替代性_ 的概念。考虑员工 #cf_span[a] 和员工 #cf_span[b]，其中 #cf_span[b] 是 #cf_span[a] 的上级（不一定是直接上级）。那么 #cf_span[a] 相对于 #cf_span[b] 的可替代性 #cf_span[r(a, b)] 定义为：在 #cf_span[b] 的所有下属（不一定是直接下属）中，等级不超过 #cf_span[a] 的人数。除了可替代性，Arkady 还引入了 _可忽略性_ 的概念。员工 #cf_span[a] 的可忽略性 #cf_span[za] 等于他相对于所有上级的可替代性之和，即对所有上级 #cf_span[b] 求和。
Arkady 不仅关心自己的可忽略性，也关心公司中所有员工的可忽略性。请为 Arkady 计算每位员工的可忽略性。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 公司中的员工数量。
第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n])，其中 #cf_span[pi = 0] 表示第 #cf_span[i] 号员工是 CEO，否则 #cf_span[pi] 表示编号为 #cf_span[i] 的员工的直接上级的编号。员工编号从 #cf_span[1] 到 #cf_span[n]。保证这些值中恰好有一个 #cf_span[0]，且 CEO 是所有其他员工的上级（不一定是直接上级）。
请输出 #cf_span[n] 个整数 —— 按员工编号顺序输出所有员工的可忽略性：#cf_span[z1, z2, ..., zn]。
考虑第一个示例：
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 公司中的员工数量。第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n])，其中 #cf_span[pi = 0] 表示第 #cf_span[i] 号员工是 CEO，否则 #cf_span[pi] 表示编号为 #cf_span[i] 的员工的直接上级的编号。员工编号从 #cf_span[1] 到 #cf_span[n]。保证这些值中恰好有一个 #cf_span[0]，且 CEO 是所有其他员工的上级（不一定是直接上级）。
## Output
请输出 #cf_span[n] 个整数 —— 按员工编号顺序输出所有员工的可忽略性：#cf_span[z1, z2, ..., zn]。
[samples]
## Note
考虑第一个示例：
CEO 没有上级，因此 #cf_span[z1 = 0]。
#cf_span[r(2, 1) = 2]（员工 #cf_span[2] 和 #cf_span[4] 满足条件，员工 #cf_span[3] 的等级过高）。因此 #cf_span[z2 = r(2, 1) = 2]。
类似地，#cf_span[z4 = r(4, 1) = 2]。
#cf_span[r(3, 2) = 1]（员工 #cf_span[3] 是 #cf_span[2] 的下属且等级合适）。#cf_span[r(3, 1) = 3]（员工 #cf_span[2]、#cf_span[3]、#cf_span[4] 满足条件）。因此 #cf_span[z3 = r(3, 2) + r(3, 1) = 4]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of employees.
Let $ p = (p_1, p_2, \dots, p_n) \in \{0, 1, \dots, n\}^n $ be the parent array, where $ p_i = 0 $ iff employee $ i $ is the CEO.
Define the manager relation: for $ i \neq j $, $ j $ is an **ancestor** of $ i $ if $ j $ lies on the unique path from $ i $ to the CEO.
Define rank: $ r(i) = 1 + \text{depth}(i) $, where $ \text{depth}(i) $ is the number of edges from $ i $ to the CEO (CEO has depth 0, so $ r(\text{CEO}) = 1 $).
For employees $ a $ and $ b $, where $ b $ is an ancestor of $ a $, define the **replaceability** of $ a $ with respect to $ b $:
$$
r(a, b) = \left| \left\{ x \in \text{subordinates}(b) \mid r(x) \leq r(a) \right\} \right|
$$
where $ \text{subordinates}(b) $ denotes the set of all descendants of $ b $ (including indirect ones).
Define the **negligibility** of employee $ a $:
$$
z(a) = \sum_{\substack{b \text{ is an ancestor of } a}} r(a, b)
$$
**Constraints**
1. $ 1 \leq n \leq 5 \cdot 10^5 $
2. $ p_i \in \{0\} \cup \{1, \dots, n\} $, with exactly one $ p_i = 0 $ (CEO)
3. The hierarchy is a tree rooted at the CEO, with all other employees having exactly one immediate manager.
**Objective**
Compute $ z(i) $ for each employee $ i \in \{1, 2, \dots, n\} $.
API Response (JSON)
{
"problem": {
"name": "E. Arkady and a Nobody-men",
"description": {
"content": "Arkady words in a large company. There are _n_ employees working in a system of a strict hierarchy. Namely, each employee, with an exception of the CEO, has exactly one immediate manager. The CEO is a",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF860E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Arkady words in a large company. There are _n_ employees working in a system of a strict hierarchy. Namely, each employee, with an exception of the CEO, has exactly one immediate manager. The CEO is a...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Arkady 在一家大型公司工作。公司中有 #cf_span[n] 名员工，采用严格的层级结构：除 CEO 外，每位员工恰好有一位直接上级。CEO 是所有员工的上级（通过直接上级的链式关系）。\n\n每位员工有一个整数等级。CEO 的等级为 #cf_span[1]，其他每位员工的等级等于其直接上级的等级加 #cf_span[1]。\n\nArkady 在公司中职位不错，但他感到自己在公司结构中无足轻重，有...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of employees. \nLet $ p = (p_1, p_2, \\dots, p_n) \\in \\{0, 1, \\dots, n\\}^n $ be the parent array, where $ p_i = 0 $ iff employee $ i $ is the ...",
"is_translate": false,
"language": "Formal"
}
]
}