Вам задано дерево из \(n\) вершин с корнем в вершине \(1\). Также на данном дереве расположена фишка. Первоначально фишка находится в корне дерева. Вы можете двигать фишку по ребрам дерева следующим образом: пусть текущая вершина с фишкой \(v\), тогда у вас есть два возможных хода:
В данной задаче считается, что корень не является листом (даже если его степень равна \(1\)). Посчитайте максимальное количество различных листов, которые вы сможете посетить одной последовательностью ходов.
В первой строке заданы два целых числа \(n\) и \(k\) (\(1 \le k < n \le 10^6\)) — количество вершин в дереве и ограничение на высоту подъема.
Вторая строка содержит \(n - 1\) целых чисел \(p_2, p_3, \dots, p_n\), где \(p_i\) — непосредственный родитель вершины \(i\).
Гарантируется, что входные данные задают дерево с корнем в вершине \(1\).
Выведите единственное целое число — максимально возможное количество различных листов, которые вы сможете посетить одной последовательностью ходов.
Граф из первого примера изображен ниже:
Один из возможных оптимальных обходов: \(1 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 7 \rightarrow 4 \rightarrow 6\).
Граф из второго примера:
Один из возможных оптимальных обходов: \(1 \rightarrow 7 \rightarrow 5 \rightarrow 8\). Заметим, что невозможно добраться из вершины \(6\) в \(7\) или \(8\) и наоборот.
7 1 1 1 3 3 4 4
4
8 2 1 1 2 3 4 5 5
2
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач