题目背景

Warning: If you submit a malicious program, you will be banned.

警告：恶意提交本题将被封号。

题目描述

Mr. Hobson has retired from running a stable and has invested in a more modern form of transport,trains. He has built a rail network with n stations. However, he has retained his commitment to free the passenger from the burden of too many choices: from each station, a passenger can catch a train to exactly one other station. Such a journey is referred to as a $leg$. Note that this is a one-way journey, and it might not be possible to get back again.

Hobson also offers exactly one choice of ticket, which allows a passenger to travel up to $k$ legs in one trip. At the exit from each station is an automated ticket reader (only one, so that passengers do not need to decide which to use). The reader checks that the distance from the initial station to the final station does not exceed $k$ legs.

Each ticket reader must be programmed with a list of valid starting stations, but the more memory this list needs, the more expensive the machine will be. Help Hobson by determining, for each station $A$, the number of stations (including $A$) from which a customer can reach $A$ in at most $k$ legs.

输入格式

The first line of input contains two integers $n$ and $k$, where $n$ $(2 \leq n \leq 5\times10^5)$ is the number of stations and $k$ $(1 \leq k \leq n − 1)$ is the maximum number of legs that may be traveled on a ticket. Then follow $n$ lines, the $i^{th}$ of which contains an integer $d_i$ $(1 \leq d_i \leq n$ and $d_i ≠ i)$, the station which may be reached from station $i$ in one leg.

输出格式

Output $n$ lines, with the $i^{th}$ line containing the number of stations from which station $i$ can be reached in at most $k$ legs.

题目大意

【题目描述】

Hobson 先生从管理马厩的工作中退休后，投资于一种更加现代的交通方式：火车。

他已经修建了一个包含 $n$ 个火车站的铁路网。然而，他兑现了让乘客摆脱选择困难症的承诺：对于每个站点，乘客只能乘坐火车前往一个站点，别无其它选择。

这样的一段旅程被称作一趟。要注意这是单向的旅程，可能无法再回到出发点。

Hobson 同样也只提供一种车票，允许乘客一次旅行的距离不超过 $k$ 趟。在每个站点的出口会有一个自动读票机（只有一个，所以乘客就不用纠结于要用哪个）。机器会检查从始发站到到达站的距离是否不超过 $k$ 趟。

每个读票机必须编入一个合法始发站列表，但是列表消耗的存储空间越多，机器就越贵。

请帮助 Hobson 先生确定：对于每个站点 $A$，能够在最多 $k$ 趟的旅程中到达 $A$ 的站点个数（包含 $A$ 本身）。

上图为样例输入 1 对应的示意图。每个圆圈代表了一个站点，圆圈旁边的数字为当 $k=2$ 时需要编入读票机的站点编号。

【输入格式】

第一行包含两个整数 $n, k$，$n$ 为站点个数，$k$ 为一张票允许旅行的最多趟数。
接下来 $n$ 行，第 $i$ 行包含一个整数 $d_i$，表示第 $i$ 个站点经过一趟到达的站点。

【输出格式】

输出 $n$ 行，第 $i$ 行输出能在 $k$ 趟内到达站点 $i$ 的站点数目。

【译者注】

在不侵犯原题版权的情况下，本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，注明出处时需指向本题链接。

Translate By @小粉兔

6 2
2
3
4
5
4
3

1
2
4
5
3
1

5 3
2
3
1
5
4

3
3
3
2
2

提示

Source: ICPC World Finals 2019.