Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | guvern.in, guvern.out | Sursă | Algoritmiada 2011, Runda Finala |
| Autor | Andrei Parvu, Cosmin Silvestru Negruseri | Adăugată de |  Andrei Parvu •andrei.12 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate | N/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ătoarele N linii conţin N numere naturale distincte, a i-a linie conţinâ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.in | guvern.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
