arbore
Se da un arbore format din n noduri în care fiecare nod are asociat un numar
natural nenul. Cerinta
Sa se selecteze din arborele initial un subgraf conex pentru care suma valorilor asociate nodurilor este egala cu un numar natural k dat. Un subgraf se obtine eliminand din graful dat noduri împreuna cu muchiile incidente cu acestea.
Date de intrare
Nodurile arborelui sunt numerotate de la 1 la n, radacina fiind nodul numerotat cu 1.
Fisierul de intrare arbore.in are urmatoarea structura:
- pe
prima linie sunt scrise numerele n
si k, separate printr-un
spatiu;
- pe cea de-a doua linie este scrisa valoarea asociata nodului 1
(radacina arborelui);
- pe cea de-a treia linie sunt scrise doua numere,
primul reprezentând nodul parinte al nodului 2, iar al doilea reprezentând
valoarea asociata nodului 2;
- pe cea de-a patra linie sunt scrise doua
numere, primul reprezentând nodul parinte al nodului 3, iar al doilea
reprezentând valoarea asociata nodului 3;
...
- pe linia n+1 sunt scrise doua numere, primul
reprezentând nodul parinte al nodului n, iar al doilea reprezentând valoarea
asociata nodului n.
Date de iesire
Fisierul arbore.out va contine o linie cu numarul -1 (daca nu exista solutie) sau, daca exista solutie, se vor afisa nodurile ce formeaza un subgraf conex care respecta cerinta problemei (câte un singur nod pe fiecare linie).
Restrictii 1 <= n <= 100
1 <= k <= 1000
1 <= valoarea asociata
unui nod <= 1000
Solutia nu este unica.
Exemplu
arbore.in |
arbore.out |
10 29 30 1 7 1 22 2 5 2 10 4 1 4 2 5 25 5 2 5 4 |
2 4 5 6 9 10 |
Timp maxim de executie pe test: 0.3 secunde