tree_infection (EJOI contest)
Time limit: 1 seconds | Memory limit: 2024 MB | Task type: batch
Algorithms: data structures, dfs, tree, tree dp, lowest common ancestor

# Tree Infection

You are given a rooted tree consisting of *N* vertices, along with integers *R* and *M*. The vertices are numbered from 1 to *N*, with vertex 1 as a root. Each of the other vertices has a single parent in the tree.

If a vertex *s* is chosen, it becomes infected along with all its descendants (i.e. vertices that can be reached by following edges downward from *s*) at a distance of *R* or less, where distance is calculated as the number of edges between vertices. A vertex *u* is considered reachable from vertex *v* if and only if neither of them is infected, and the number of infected vertices on the path between them does not exceed *M*.

For each possible chosen vertex *s* (1 ≤ *s* ≤ *N*), you must calculate the number of vertex pairs (*u*, *v*) such that 1 ≤ *u* < *v* ≤ *N* and *u* is reachable from *v* (and vice versa).

## Input Format

The first line contains three integers: *N*, *R* and *M*.

The second line contains *N* − 1 integers: *p*[2], *p*[3], ... ,*p*[*N*], the parents of the vertices 2, 3, ... ,*N*, respectively.

## Output Format

Print *N* lines with single integer each: *s*-th line should contain required number of pairs when the chosen vertex is *s*.

**It's not recommended to use `std::endl` for outputting newline symbols. Instead, consider using `\n` for better performance.**

#### Example 1

| Standard input            | Standard output |
|---------------------------|-----------------|
| 13 2 2                    | 16              |
| 1 2 3 4 3 6 6 8 2 10 11 1 | 4               |
|                           | 15              |
|                           | 55              |
|                           | 66              |
|                           | 36              |
|                           | 66              |
|                           | 55              |
|                           | 66              |
|                           | 45              |
|                           | 55              |
|                           | 66              |
|                           | 66              |

![Example Tree](infection (1 of 3).jpeg)

The image above corresponds to *s* = 2.

The reachable pairs are: (1,13), (7,8), (7,9), (8,9).

This list doesn't include the pair (1,2) since vertex 2 is infected. Similarly, the pair (1,5) is absent since the path between 1 and 5 has three infected vertices (2, 3 and 4).

#### Example 2

| Standard input | Standard output |
|----------------|-----------------|
| 3 0 1          | 1               |
| 1 2            | 1               |
|                | 1               |

#### Constraints

- 2 ≤ *N* ≤ 500 000
- 1 ≤ *p*[*i*] < *i* (for each 2 ≤ *i* ≤ *N*)
- 0 ≤ *R* ≤ *N* − 1
- 0 ≤ *M* ≤ 2 × *R* + 1

#### Subtasks

- 1. (20 points) *N* ≤ 300
- 2. (14 points) *R* = 0
- 3. (15 points) *M* = 2 × *R* + 1
- 4. (10 points) *M* = 2 × *R* − 1
- 5. (16 points) *N* ≤ 5 000
- 6. (25 points) No additional constraints.

Starter code:

Grader code:

Setup script:

Evaluation script: