#include #include using namespace std; int res = 0, N, K; vector *children; // Vrací vyškolenost vrcholu // <= 0 -> hloubka, kterou je potřeba pokrýt // >= 0 -> "přebytek" pokrytí int dfs(int v) { int max = 0, min = 0; for (int u : children[v]) { int h = dfs(u); min = min < h ? min : h; max = max > h ? max : h; } if (min + max > 0) // Nemusíme nic řešit, hloubku vyřeší přebytky return max - 1; if (min == -K) { // Musíme přidat vrchol -> BÚNO kořen stromu res++; return K; } // Odkládáme řešení na později return min - 1; } int main (int argc, char ** argv) { cin >> N >> K; children = new vector [N]; int j; for (int i = 1; i < N; i++) { cin >> j; children[j].push_back(i); } if (dfs(0) < 0) // Přidáme kořen celého stromu, pokud něco zbyde res++; cout << res << endl; }