Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbkset.in, arbkset.out | Sursă | ACM ICPC Faza Nationala 2015 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Comisie ICPC UPB •neapuiu |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbkset
Se da un arbore cu N noduri numerotate de la 1 la N, avand radacina in nodul 1. Fiecare nod i ($1≤i≤N$) are asociata o valoare v(i). Se doreste selectarea unei multimi de exact K noduri, astfel incat:
* oricare doua noduri din multime nu sunt vecine in arbore (adica pentru orice doua noduri i si j din multime, nici i nu este parintele lui j, si nici j nu este parintele lui i)
* suma valorilor asociate celor K noduri din multime este maxima
Date de intrare
Fişierul de intrare arbkset.in contine pe prima linie numarul T, reprezentand numarul de teste din fisier. Urmeaza apoi cele T teste. Fiecare test este descris pe 3 linii din fisier. Pe prima linie se afla numerele N si K. Pe a doua linie se afla N-1 numere, reprezentand, in ordine, parintii nodurilor 2, ..., N. Pe a treia linie se afla N numere, reprezentand, in ordine, valorile v(1), ..., v(N).
Date de ieşire
În fişierul de ieşire arbkset.out veti afisa T linii. Pe a i-a linie veti afisa suma maxima a valorilor asociate unei multimi ce respecta conditiile din enunt. In cazul in care o astfel de multime nu exista, afisati -1.
Restricţii
- 2 ≤ N ≤ 15000
- 1 ≤ K ≤ min(N,1000)
- 1 ≤ v(i) ≤ 10000
- Parintele unui nod i este mereu unul din nodurile 1,...,i-1.
Exemplu
| arbkset.in | arbkset.out |
|---|---|
| 3 2 1 1 10 20 2 2 1 10 20 5 4 1 2 2 2 1 10 1 1 1 | 10 -1 4 |
Explicaţie
In primul test se alege multimea ce contine doar nodul 2.
In al doilea test nu se poate selecta o multime cu 2 noduri avand proprietatile cerute in enunt.
In al treilea test se alege multimea ce consta din nodurile 1, 3, 4 si 5.
