Problem Description

You are given a rooted tree $T$ with $N$ nodes, where the root is guaranteed to be node $1$.

A node $s$ on the tree will be chosen. All nodes whose distance to $s$ is not greater than $R$ will be infected, where the distance between two nodes is defined as the number of edges on the path between them in the tree.

A pair of nodes is reachable if and only if both nodes are not infected, and the number of infected nodes on the path between them is not greater than $M$.

For $s=1,2,\cdots,N$, compute the number of reachable pairs of nodes when choosing $s$.

Input Format

The first line contains three integers $N,R,M$.

The second line contains $N-1$ integers $p_2,p_3,\cdots,p_N$, representing the parent of each node.

Output Format

Output $N$ lines, each containing one integer. The integer on line $s$ represents the answer when choosing $s$.

13 2 2
1 2 3 4 3 6 6 8 2 10 11 1

16
4
15
55
66
36
66
55
66
45
55
66
66

3 0 1
1 2

1
1
1

Hint

[Sample Explanation]

The tree for $s=2$ is shown in the figure.

All reachable pairs are $(1,13)$, $(7,8)$, $(7,9)$, and $(8,9)$.

Note that $(1,2)$ is not reachable because $2$ is already infected; $(1,5)$ is not reachable because there are three infected nodes $2,3,4$ on the path.

[Constraints]

This problem uses bundled tests.

• Subtask 1 (20 pts): $N\leq 300$.
• Subtask 2 (14 pts): $R=0$.
• Subtask 3 (15 pts): $M=2R+1$.
• Subtask 4 (10 pts): $M=2R-1$.
• Subtask 5 (16 pts): $N\leq 5\times 10^3$.
• Subtask 6 (25 pts): No special constraints.

For $100\%$ of the testdata, it is guaranteed that $2\leq N\leq 5\times 10^5$, $1\leq p_i<i$, $0\leq R\leq N-1$, $0\leq M\leq 2R+1$.

Translated by ChatGPT 5