BAC · Arbori (ușor) · clasa a 8-a
Câți descendenți are un nod
Cerință
Afișează câți descendenți are nodul k (toate nodurile din subarborele său, fără el însuși).
Problemă originală de antrenament, nu este subiect oficial.
Date de intrare
Pe prima linie se află n. Pe a doua linie vectorul de tați t[1..n] (t[i] = 0 pentru rădăcină). Pe a treia linie se află k.
Date de ieșire
Un singur număr. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ k ≤ n ≤ 5000
- Sunt 20 de teste, fiecare valorează 5 puncte.
3 2 3 0 3
2
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Numără nodurile din subarborele lui k: suma dimensiunilor subarborilor fiilor, plus fiii. Rezultatul corect pentru acest exemplu este: 2.
4 2 4 4 0 3
0
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Numără nodurile din subarborele lui k: suma dimensiunilor subarborilor fiilor, plus fiii. Rezultatul corect pentru acest exemplu este: 0.
8 4 0 4 2 8 4 4 2 7
0
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Numără nodurile din subarborele lui k: suma dimensiunilor subarborilor fiilor, plus fiii. Rezultatul corect pentru acest exemplu este: 0.