Гусеница решила побывать в каждой вершине дерева. Изначально она сидит в корне.
Дерево представлено как корневое дерево с корнем в вершине \(1\). Каждое переползание в соседнюю вершину у неё занимает \(1\) минуту.
А под деревом стоит батут. Если гусеница отцепится от дерева и упадёт на батут, то за \(0\) секунд окажется в корне дерева. Но батут старый и выдержит не более \(k\) падений гусеницы.
За какое минимальное время гусеница сможет обойти дерево?
Более формально — надо найти минимальное время, нужное, чтобы посетить все вершины дерева, если гусеница начинает в корне (вершине \(1\)) и двигается с помощью двух способов.
- Перейти по ребру в одну из соседних вершин: тратит \(1\) минуту.
- Телепортироваться в корень: не тратит времени, никакие новые вершины не становятся посещёнными.
Второй способ (телепортацию) можно применить не более \(k\) раз. Гусеница может закончить путешествие в любой вершине.