== include(page="template/taskheader" task_id="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!
Poveste şi cerinţă...
h2. 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$.
Fişierul de intrare $guvern.in$ ...
h2. 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.
În fişierul de ieşire $guvern.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 200 000$
* $-10^9^ ≤ gradul de cooperare al unui ministru ≤ 10^9^$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. guvern.in |_. guvern.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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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
...
== include(page="template/taskfooter" task_id="guvern") ==
