Переписка с другом
Иногда вспоминаешь старого друга и начинаешь вспоминать все, что с ним связано. Хорошо, что есть социальные сети: они хранят вашу переписку с самого знакомства, и можно с легкостью прочитать, о чем же вы спорили 10 лет назад.
Формально, ваша переписка — упорядоченная по времени последовательность сообщений, пронумерованных от 1 до n, где n — общее количество сообщений в переписке.
Каждое сообщение может содержать ссылку на более раннее сообщение, на которое оно является ответом. При открытии сообщения с номером x или при переходе по ссылке на сообщение с номером x диалог показывается так, что видны k сообщений до этого сообщения, само сообщение x и k сообщений после этого сообщения. Если до или после текущего сообщения было менее k сообщений, то все они отображаются.
Изучая старую переписку, вы всегда читаете все сообщения, показанные на экране, а затем переходите по ссылке в текущем сообщении x (в которое пришли по ссылке), если такая есть, и читаете дальше.
Определите количество различных сообщений, которые вы прочтете, если начинать читать переписку, открыв диалог на сообщении t, для каждого t от 1 до n. Считайте ответ для каждого случая независимо. Если начинать читать с сообщения номер x, то на экране изначально показаны k сообщений до сообщения x, само сообщение x и k сообщений после. Сообщения, прочитанные несколько раз, считаются за одно.
В первой строке следуют два целых числа n и k (1 ≤ n ≤ 105, 0 ≤ k ≤ n) — количество сообщений в переписке и количество сообщений, которые видны сверху и снизу от текущего.
Во второй строке следует последовательность целых чисел a1, a2, ..., an (0 ≤ ai < i), где ai равно нулю, если из сообщения i нет ссылки в предыдущее сообщение, либо ai равно номеру сообщения, в которое можно перейти по ссылке из сообщения i. Все сообщения перечислены в хронологическом порядке. Гарантируется, что если в сообщении с номером x есть ссылка, то она ведёт в сообщение с номером меньшим, чем x.
Выведите n целых чисел, где i-е число должно быть равно количеству различных сообщений, которые можно прочитать, если начинать читать с i-го сообщения и переходить по ссылкам до тех пор, пока это возможно.
6 0
0 1 1 2 3 2
1 2 2 3 3 3
10 1
0 1 0 3 4 5 2 3 7 0
2 3 3 4 5 6 6 6 8 2
2 2
0 1
2 2
Если начинать с шестого сообщения в первом примере, то вы прочитаете шестое сообщение, затем второе, затем первое и закончите, т. к. из первого сообщения нет ссылки.
Если начинать с шестого сообщения во втором примере, то вы сначала прочтете пятое, шестое и седьмое сообщение, затем перейдете по ссылке в пятое сообщение и прочтете четвертое, пятое и шестое сообщение, затем перейдете по ссылке в четвертое сообщение и прочитаете третье, четвертое и пятое сообщение, наконец, перейдете по ссылке в третье сообщение и прочитаете второе, третье и четвертое сообщение. Больше переходить по ссылкам вы не будете, так как из третьего сообщения ссылки нет. Итого вы прочтете все сообщения со второго по седьмое, таких шесть.
Задача на Codeforces (контест 928, задача B, © Codeforces.com)