Arkady and a Nobody-men
Contest: Codeforces Round 434 (Div. 1, based on Technocup 2018 Elimination Round 1)
Difficulty rating: 2700
Tags: data structures, dfs and similar, trees

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 za of employee a equals the sum of his replaceabilities with respect to all his managers, i.e. $$z_{a} = \sum_{b} r(a,b)$$, 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 format:
The first line contains single integer n (1 ≤ n ≤ 5·105) — the number of employees in the company.

The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n), where pi = 0 if the i-th employee is the CEO, otherwise pi 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 format:
Print n integers — the negligibilities of all employees in the order of their ids: z1, z2, ..., zn.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the first example:

- The CEO has no managers, thus z1 = 0.
- r(2, 1) = 2 (employees 2 and 4 suit the conditions, employee 3 has too large rank). Thus z2 = r(2, 1) = 2.
- Similarly, z4 = 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 z3 = r(3, 2) + r(3, 1) = 4.

Example input:
4
0 1 2 1

Example output:
0 2 4 2

Example input:
5
2 3 4 5 0

Example output:
10 6 3 1 0

Editorial:
1. First of all, ans[v] = ans[parent[v]] + depth[v] + ans'[v], where ans'[v] is the sum of (number of descendants of the rank depth[v]) for all predecessors of v. All we need is to compute ans'[v] now.
2. Let's make a dfs in the graph. Let the dfs(v) return a vector ret[v] such that ret[v][d] is the following tuple: (number of vertices on depth d in subtree of v, some vertex x with depth d in the subtree of v, the ans'[x] if we consider only predecessors in the subtree of v). Also let's build some structure so that we can easily restore answers in this subtree if we know the final value of ans'[x]. We will see what is this structure later.
3. To compute ret[v] we need to be able to merge two rets of its sons. Let's say we merge tuple (cnta, a, ans'[a]) with (cntb, b, ans'[b]). Then all we need to do is:   ans'[b] +  = depth[v] * cnta,  ans'[a] +  = depth[v] * cntb,  return (cnta + cntb, a, ans'[a]) as the result.  However, we must also be able to restore ans'[b] after the dfs is complete (remind the unknown structure). So after performing ans'[b] +  = depth[v] * cnta let's add an edge a → b to a new graph with weight ans'[a] - ans'[b]. Note that the difference between these values will be the same all the time after the tuples are merged, so using this edge we will be able to restore the answer ans'[b].
4. ans'[b] +  = depth[v] * cnta,
5. ans'[a] +  = depth[v] * cntb,
6. return (cnta + cntb, a, ans'[a]) as the result.
7. After the dfs is done, run another dfs on the new graph to restore the values ans'[v] and then ans[v].
8. To perform the second step fast, we need to note that we can always merge smaller rets into larger, and move them in O(1) into parents. Since each tuple is merged into a larger vector only once, this solution works in total in O(n).