Jump_Civilization — RMI contest
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 21
Algorithms: data structures, tree, interval dp, dynamic programming

# Problem: Jump Civilization

Romanian Master of Informatics, Day 2
Bucharest, Romania
Friday 29th November, 2024

Input file: `stdin`
Output file: `stdout`

> "Here in Parkour Jump Civilization, No One Chooses to Jump for the Beef"

Evbo — Parkour Civilization, the movie

In jump civilization, the world consists of $N$ floating islands, numbered 1 to $N$. When at island $i$ (for $1 \le i \le N$), the members of jump civilization can either take:

- an easy jump, from island $i$ to island $i + 1$; or
- a difficult jump, from island $i$ to island $v_i$, where $i < v_i \le N$.

In order to rank up in jump civilization, the members of jump civilization need to compute the "jumping power" of each island. The jumping power of island $i$ is the number of islands which can be reached by starting at island $i$ and using at most $K$ jumps.

The previous Jump Champion, wanting to make sure that the jumping course is fair, instituted the following important rule: "Whenever $1 \le i < j \le N$, either $v_i \le j$ or $v_j \le v_i$."

You, as an aspiring member of jump civilization, want to find the jumping power of every island — can you do this efficiently?

## Input data

The first line of the input contains two space-separated integers $N$, $K$. The second line of the input contains $N - 1$ space-separated integers $v_1, \dots, v_{N-1}$.

## Output data

Output $N$ space-separated integers, the jumping power of the islands in order.

## Restrictions

- $1 \le N \le 300\,000$
- $1 \le K \le N - 1$
- $i < v_i \le N$
- For $1 \le i < j \le N$, either $v_i \le j$ or $v_j \le v_i$.
- If island $j$ can be reached from island $i$ in two different ways using at most $K$ jumps, then the island is only counted once for the jumping power of island $i$.
- When computing the jumping power of an island, it doesn't matter whether we use easy or difficult jumps — only the number of jumps matters.

![](_page_1_Picture_1.jpeg)

## Examples

| #   | Points | Restrictions                     |
| --- | ------ | -------------------------------- |
| 1   | 6      | $N \le 2000$                     |
| 2   | 27     | $N \le 100\,000$ and $K \le 50$   |
| 3   | 11     | $v_i \le i + 2$ for $1 \le i < N$ |
| 4   | 37     | $N \le 100\,000$                  |
| 5   | 19     | No further restrictions.         |

#### Examples

| Input file | Output file | Explanations                                                                                                                                                                                                                                                  |
| :--------- | :---------- | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |
| `5 1`<br>`4 3 4 5` | `3 2 2 2 1` | From island 1, one can<br>reach island 1 without<br>jumping, and islands 2 and<br>4 with 1 jump. In total,<br>the jumping power of island<br>1 is 3.                                                                                                                                  |
| `6 2`<br>`2 3 5 5 6` | `3 4 4 3 2 1` |                                                                                                                                                                                                                                                        |

Starter code: