P11885 [RMI 2024] 跑酷 / Jump Civilization

有 $n$ 个岛，编号 $1\sim n$。给定长度为 $(n-1)$ 的正整数数列 $v_1,v_2,\ldots,v_{n-1}$。 当你在岛 $i$（$1\le i\lt n$）上时，可以跳到岛 $(i+1)$ 上或者岛 $v_i$ 上。这里，$i\lt v_i$。 给定正整数 $k$。对于岛 $i$，定义 $f(i,k)$ 表示从它出发跳**至多** $k$ 步能够跳到的岛有多少个（包括自身）。 此外，$v_i$ 还满足**特殊性质**：**对于任意 $1\le i\lt j\lt n$，要么 $v_i\le j$，要么 $v_j\le v_i$。** 对于 $i=1,2,\ldots,n$，求出 $f(i,k)$。 补充说明：即使岛 $i$ 有多种在 $k$ 步内跳到岛 $j$ 的方式，岛 $j$ 也只算一次。

第一行，两个正整数 $n,k$。 第二行，$(n-1)$ 个正整数 $v_1,v_2,\ldots,v_{n-1}$。

输出一行 $n$ 个正整数，第 $i$ 个数表示 $f(i,k)$。

### 样例解释 - 样例 $1$ 解释：以岛 $1$ 为例，跳 $0$ 步可以到达岛 $1$，跳 $1$ 步可以到达岛 $\{2,4\}$。所以 $f(1,1)=3$。 ### 数据范围 对于 $100\%$ 的数据，保证： - $1\le n\le 3\times 10^5$； - $1\le k\lt n$； - $i\lt v_i\le n$； - **对于任意 $1\le i\lt j\lt n$，要么 $v_i\le j$，要么 $v_j\le v_i$。** --- | 子任务 | $n\le$ | 特殊性质 | 得分 | | :-: | :-: | :-: | :-: | | $1$ | $2\, 000$ | | $6$ | | $2$ | $10^5$ | $\text{A}$ | $27$ | | $3$ | $3\times 10^5$ | $\text{B}$ | $11$ | | $4$ | $10^5$ | | $37$ | | $5$ | $3\times 10^5$ | | $19$ | - 特殊性质 $\text{A}$：$k\le 50$。 - 特殊性质 $\text{B}$：$v_i\le i+2$。