Diferențe pentru problema/profit între reviziile #8 si #18

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

Sunt $N$ orașe in Olympiland, numerotate de la $1$ la [$N$]. Unele sunt direct conectate și rețeaua de drumuri este  organizată în așa mood încât există un singur drum posibil de la un oraș la altul, care poate să nu fie neapărat direct (trecând prin alte orașe).
Pentru a realiza un mare proiect de infrastructură, a fost creată o lisă a rutelor pentru a transporta echipamentul necesar pentru acest proiect. Un singur transport o sa fie efectuat pe fiecare rută. Un drum este definit de doua orase u si v intre care sunt transportate echipamentele  (direcția nu este importantă) și un profit p realizat de către compania care o să facă transportul pe ruta respectivă.

Sunt $N$ orașe in Olympiland, numerotate de la $1$ la [$N$]. Unele sunt direct conectate. Există un singur drum posibil de la un oraș la altul, care poate să nu fie neapărat direct (trecând prin alte orașe).
Pentru a realiza un mare proiect de infrastructură, a fost creată o lisă a rutelor care pot fi utilizate pentru a transporta echipamentul necesar acestui proiect. Un singur transport o sa fie efectuat pe fiecare rută. Un drum este definit de doua orase $u$ si $v$ intre care sunt transportate echipamentele (direcția nu este importantă) și un profit $p$ realizat de către compania care o să facă transportul pe ruta respectivă.

Este organizat un concurs pentru companiile care efectuează transportul. Fiecare companie trebuie să aleagă doua orașe și trebuie să finalizeze transportul echipamentelor pe toate rutele care încep și se termină între cele două orașe inclusiv. Scrieți un program care să aleagă doua orașe din Olympiland pentru a obține profit maxim prin utilizarea rutelor care se află între cele două orașe selectate.

Este organizat un concurs pentru companiile care efectuează transportul. Fiecare companie trebuie să aleagă doua orașe și trebuie să finalizeze transportul echipamentelor pe toate rutele care încep și se termină între cele două orașe (inclusiv acestea). Scrieți un program care să aleagă doua orașe din Olympiland pentru a obține profit maxim prin utilizarea rutelor care se află între cele două orașe selectate.

h2. Date de intrare

Fișierul de intrare $profit.in$ conține un număr întreg $N$ reprezentând numărul de orașe din Olymliland. Fiecare din următoarele $N - 1$ linii, conține două numere întregi pozitive (nu mai mari decât [$N$]), separate prin spații, reprezentând o pereche de orașe care sunt direct conectate de către un drum. Următoarea linie conține numărul întreg $M$ reprezentând lungimea listei cu drumurile de transport. Următoarele $M$ linii conțin trei întregi pozitivi separați prin spații, reprezentând numerele celor două orașe, stabilind ruta și profitul realizat.

Fișierul de intrare $profit.in$ conține un număr întreg $N$ reprezentând numărul de orașe din Olympiland. Fiecare din următoarele $N - 1$ linii, conține două numere întregi pozitive (nu mai mari decât [$N$]), separate prin spații, reprezentând o pereche de orașe care sunt direct conectate de către un drum. Următoarea linie conține numărul întreg $M$ reprezentând lungimea listei cu drumurile de transport. Următoarele $M$ linii conțin trei întregi pozitivi separați prin spații, reprezentând numerele celor două orașe, ruta și profitul realizat.

h2. Date de ieșire

h2. Restricții

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

* $2 ≤ N ≤ 10[^5^]$
* $0 ≤ M ≤ 10[^5^]$
* $1 ≤ profitul fiecărei rute ≤ 10[^3^]$

În 20% of the tests :  N < 100.
In 40% of the tests :  N < 1000.
In 70% of the tests there exists an optimal path, including the first direct road, given in the
list of direct roads in Olympiland.

* $În 20% dintre teste :  N < 100$
* $În 40% dintre teste :  N < 1 000$
* $În 70% dintre teste există o rută optimă, inclusiv drumul direct dat in lista drumurilor directe$

h2. Exemplu
table(example).

|_. profit.in |_. profit.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

|_. profit.in |_. profit.out |_. Explicație |
| 6
1 2
2 3
2 4
5 4
6 4
4
1 4 10
2 5 20
6 3 15
2 1 1.
| 5 1 31
| !{width:60%}problema/profit?profit.png!
|

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