== include(page="template/taskheader" task_id="spiridusi") ==
Mei şi Satsuki s-au întors de curând în casa de vacanţă a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s i spiriduşi de praf.
Mei şi Satsuki s-au întors de curând în casa de vacanţă a familiei lor. Această casă este formată din $N$ camere, unite între ele prin $N-1$ culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera $1$. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră $i$ s-au stabilit $s{~i~}$ spiriduşi de praf.
Cele două fete doresc să-şi amenajeze un spaţiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere $a$ şi $b$ (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera $b$ trece prin camera $a$. Fetele vor merge apoi din camera $a$ în camera $b$ pe drumul cel mai scurt (fără a trece de două ori prin aceeaşi cameră), gonind spiriduşii de praf aflaţi în fiecare cameră prin care trec, inclusiv pe cei din camerele $a$ şi $b$. După ce fetele ajung în camera $b$, ele consideră că toate camerele din care au gonit spiriduşii de praf au fost alese pentru spaţiul de joacă.
Fetele au stabilit pentru fiecare cameră $i$ un coeficient $p{~i~}$ care reprezintă cât de plăcută ar fi camera $i$ pentru spaţiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de $C$ spiriduşi ai prafului din camerele prin care trec.
h2. Cerinta
Cunoscând valorile lui $N$ şi $C$, numărul de spiriduşi ai prafului $s{~i~}$ , coeficienţii $p{~i~}$ pentru fiecare cameră $i$, cât şi modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienţilor $p$ ai camerelor alese pentru un spaţiu de joacă ce respectă condiţiile impuse de Mei şi Satsuki.
h2. Date de intrare
Fişierul de intrare $spiridusi.in$ ...
Pe prima linie a fişierului de intrare $spiridusi.in$ se vor afla două numere naturale $N$ şi $C$ cu semnificaţia din enunţ. Pe a doua linie se vor afla $N$ numere naturale separate prin câte un spaţiu, al $i$-lea dintre acestea reprezentând numărul de spiriduşi $s{~i~}$ aflaţi în camera $i$. Pe a treia linie se vor afla $N$ numere întregi separate prin câte un spaţiu, al $i$-lea dintre acestea reprezentând coeficientul $p{~i~}$ al camerei $i$. Pe următoarele $N-1$ linii se vor afla câte două numere întregi $x$ şi $y$ separate printr-un spaţiu, semnificând existenţa unui culoar ce uneşte camerele $x$ şi $y$.
h2. Date de ieşire
În fişierul de ieşire $spiridusi.out$ ...
În fişierul de ieşire $spiridusi.out$ se va afişa o singură linie conţinând un singur număr natural, reprezentând suma maximă a coeficienţilor $p$ ai camerelor alese pentru un spaţiu de joacă ce respectă condiţiile impuse de Mei şi Satsuki.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ C ≤ 20 000 000$
* $1 ≤ s{~i~} ≤ 20 000 000$, pentru orice i, $1 ≤ i ≤ N$.
* $-10000 ≤ p{~i~} ≤ 10000$, pentru orice i, $1 ≤ i ≤ N$.
* Pentru $20%$ din teste, fiecare cameră are maximum $2$ vecini.
* Pentru $30%$ din teste, $N ≤ 1 000$.
* Se garantează că pentru orice cameră $x$, numărul total de spiriduşi aflaţi în camerele de pe drumul cel mai scurt de la camera $1$ la camera $x$ nu depăşeşte $1 000 000 000$.
h2. Exemplu
table(example). |_. spiridusi.in |_. spiridusi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 8
2 4 6 2 4 1
3 10 11 -2 4 5
1 2
2 3
2 4
4 5
4 6
| 13
|
h3. Explicaţie
...
Dacă alegem camerele $a = 2$ şi $b = 6$, obţinem un spaţiu de joacă format din camerele $2, 4$ şi $6$.
Numărul total de spiriduşi goniţi din aceste camere este $4 + 2 + 1 = 7$, care este mai mic sau egal decât $C = 8$.
Suma coeficienţilor $p$ ai acestor camere este $10 + (-2) + 5 = 13$, maximul posibil ce se poate obţine.
== include(page="template/taskfooter" task_id="spiridusi") ==
