Fişierul intrare/ieşire:guvern.in, guvern.outSursăAlgoritmiada 2011, Runda Finala
AutorAndrei Parvu, Cosmin Silvestru NegruseriAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.2 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Guvern

Din pricina tuturor abilităţilor speciale pe care le-a arătat până acum, TractoMarm a fost angajat de Serviciile Secrete sa spioneze guvernul unei ţări străine. Guvernul este format din N miniştii, aflaţi într-o ierarhie sub formă de arbore (graf conex aciclic neorientat), în care nodul 1 reprezintă rădăcina (primul ministru). Pentru fiecare ministru se cunoaşte un număr, reprezentând gradul de cooperare al acestuia cu Serviciile Secrete. TractoMarm trebuie să selecteze o mulţime cât mai mare de miniştrii dintre cei N, respectând simultan următoarele cerinţe ale Serviciilor Secrete: 1. un ministru selectat trebuie sa aibă gradul de cooperare mai mare decat toţi ministrii selectaţi aflaţi in subordinea lui; 2. fie y gradul de cooperare al unui ministru selectat (fie acesta x); dintre toti miniştrii pe drumul de la x la 1 trebuie selectat cel care are gradul de cooperare minim şi mai mare sau egal decât y.
Dacă doriţi să îi luaţi locul lui TractoMarm, trebuie să vă arătaţi vrednici şi să rezolvaţi această problema!

Date de intrare

Fişierul de intrare guvern.in conţine pe prima linie N, numărul de miniştrii. Pe următoarele N - 1 linii se vor afla perechi de numere (x, y) reprezentând ca există o relaţie directă între miniştrii x si y.
Următoarea linie conţine N numere naturale distincte, al i-lea număr reprezentând gradul de cooperare al ministrului i.

Date de ieşire

În fişierul de ieşire guvern.out va fi afişată o singură linie, reprezentând numărul maxim de miniştrii pe care îi poate selecta, conform regulilor Serviciilor Secrete.

Restricţii

  • 1 ≤ N ≤ 200 000
  • -109 ≤ gradul de cooperare al unui ministru ≤ 109

Exemplu

guvern.inguvern.out
10
3 2
10 1
8 7
7 9
2 8
4 6
10 7
5 3
2 6
9 15 2 11 4 12 5 7 3 17
4

Explicaţie

Două soluţii posibile ar fi:
1. Sunt selectaţi miniştrii cu numerele de ordine 4 6 2 10
2. Sunt selectaţi miniştrii cu numerele de ordine 3 9 7 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content