paznici3

Paznici 3

== include(page="template/taskheader" task_id="paznici3") ==

Poveste şi cerinţă...

Se da un arbore cu $N$ noduri si $M$ paznici. Pentru a angaja paznicul $i$ trebuie sa platesti costul $Z{~i~}$. Se stie ca daca angajezi paznicul $i$, atunci acesta va pazi toate nodurile de pe lantul de la nodul $A{~i~}$ pana la nodul $B{~i~}$. Se cere sa se determine costul minim pentru a pazi tot arborele. Un nod nu are voie sa fie pazit de mai mult de un paznic.

h2. Date de intrare

Fişierul de intrare $paznici3.in$ ...

Fişierul de intrare $paznici3.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$ cu semnificatia din enunt. Pe urmatoarele $N - 1$ linii se vor afla cate $2$ numere $a$ si $b$ cu semnificatia ca exista muchie de la $a$ la $b$. Pe urmatoarele $M$ linii se vor afla cate $3$ numere $Z{~i~}$, $A{~i~}$ si $B{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $paznici3.out$ ...

Fişierul de ieşire $paznici3.out$ va contine un singur numar natural reprezentand costul minim cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* valorile elementelor sunt pana in $10.000$
* se garanteaza ca exista solutie
 

h2. Exemplu
table(example). |_. paznici3.in |_. paznici3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 6
1 2
2 3
2 4
1 5
5 6
5 7
8 3 7
7 4 4
8 6 6
9 3 4
10 6 7
5 1 1
| 23

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="paznici3") ==

8738