arbkset

Arbkset

== 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") ==