Nu aveti permisiuni pentru a descarca fisierul grader_test13.ok

 

Fişierul intrare/ieşire:paznici3.in, paznici3.outSursăAlgoritmiada 2013, Runda 3
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu •eudanip
Timp execuţie pe test0.6 secLimită de memorie66432 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Paznici3

Se da un arbore cu N noduri si M paznici. Pentru a angaja paznicul i trebuie sa platesti costul Zi. Se stie ca daca angajezi paznicul i, atunci acesta va pazi toate nodurile de pe lantul de la nodul Ai pana la nodul Bi. 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.

Date de intrare

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 Zi, Ai si Bi.

Date de ieşire

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

Restricţii

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

Exemplu

paznici3.inpaznici3.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content