Fişierul intrare/ieşire:arbkset.in, arbkset.outSursăACM ICPC Faza Nationala 2015
AutorMugurel Ionut AndreicaAdăugată deneapuiuComisie ICPC UPB neapuiu
Timp execuţie pe test5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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 intregi, 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

  • 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.

Exemplu

arbkset.inarbkset.out
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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?