| Codeforces Round 922 (Div. 2) |
|---|
| Закончено |
Гусеница решила побывать в каждой вершине дерева. Изначально она сидит в корне.
Дерево представлено как корневое дерево с корнем в вершине $$$1$$$. Каждое переползание в соседнюю вершину у неё занимает $$$1$$$ минуту.
А под деревом стоит батут. Если гусеница отцепится от дерева и упадёт на батут, то за $$$0$$$ секунд окажется в корне дерева. Но батут старый и выдержит не более $$$k$$$ падений гусеницы.
За какое минимальное время гусеница сможет обойти дерево?
Более формально — надо найти минимальное время, нужное, чтобы посетить все вершины дерева, если гусеница начинает в корне (вершине $$$1$$$) и двигается с помощью двух способов.
- Перейти по ребру в одну из соседних вершин: тратит $$$1$$$ минуту.
- Телепортироваться в корень: не тратит времени, никакие новые вершины не становятся посещёнными.
Второй способ (телепортацию) можно применить не более $$$k$$$ раз. Гусеница может закончить путешествие в любой вершине.
В первой строке входных данных находятся два целых числа: $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) — количество вершин в дереве, и $$$k$$$ ($$$0 \le k \le 10^9$$$) — максимальное число телепортаций в корень.
Во второй строке записаны $$$n-1$$$ целых чисел $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$) — предки в дереве для вершин $$$2, 3, \ldots, n$$$; вершина $$$1$$$ — корень.
В единственной строке выведите одно число — минимальное число минут, за которое можно побывать во всех вершинах дерева.
8 1 1 1 2 2 4 3 3
9
4 0 4 4 1
4
На картинке показан один из способов обойти дерево из первого теста за 9 минут.
