== include(page="template/taskheader" task_id="arbkset") ==
Poveste şi cerinţă...
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
h2. Date de intrare
Fişierul de intrare $arbkset.in$ ...
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 intregi, reprezentand, in ordine, valorile $v(1), ..., v(N)$.
h2. Date de ieşire
În fişierul de ieşire $arbkset.out$ ...
Î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$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 15$
* $2 ≤ N ≤ 15000$
* $1 ≤ K ≤ min(N,1000)$
* $1 ≤ v(i) ≤ 10000$
* Parintele unui nod $i$ este mereu unul din nodurile $1,...,i-1$.
h2. Exemplu
table(example). |_. arbkset.in |_. arbkset.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3
2 1
1
10 20
2 2
1
10 20
5 4
1 2 2 2
1 10 1 1 1
|20
-1
4
|
h3. 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.
== include(page="template/taskfooter" task_id="arbkset") ==
