Bacalaureat · Grafuri și arbori · clasa a 12-a
Este strămoș?
Cerință
Se dau vectorul de tați și două noduri x și y. Afișează DA dacă x este strămoș al lui y (se află pe drumul de la y la rădăcină, x ≠ y), altfel NU.
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 x și y.
Date de ieșire
DA sau NU. Nu afișa mesaje suplimentare.
Restricții
- 1 ≤ x, y ≤ n ≤ 3000
- Sunt 20 de teste, fiecare valorează 5 puncte.
3 2 0 2 2 3
DA
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Urcă din y din tată în tată până la rădăcină și verifică dacă întâlnești x. Rezultatul corect pentru acest exemplu este: DA.
5 0 1 2 1 1 2 1
NU
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Urcă din y din tată în tată până la rădăcină și verifică dacă întâlnești x. Rezultatul corect pentru acest exemplu este: NU.
10 5 4 2 9 0 4 9 9 1 5 10 2
NU
Datele exemplului respectă formatul de intrare. Aplicăm ideea: Urcă din y din tată în tată până la rădăcină și verifică dacă întâlnești x. Rezultatul corect pentru acest exemplu este: NU.