== 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
Each of the next
M
l
ines contains three space separated positive integers: the numbers of the
two towns, defining the route, and the profit of its realization.
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
În fișierul de ieșire $profit.out$ ...
În fișierul de ieșire $profit.out$ conține trei numere întregi separate prin spații reprezentând numerele celor două orașe cu ajutorul cărora se poate ajunge la profit maxim urmat de valoarea profitului maxim. Dacă există mai multe soluții, se va afișa oricare soluție corectă.
h2. Restricții
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 10[^5^]$
* $0 ≤ M ≤ 10[^5^]$
* $1 ≤ profitul fiecărei rute ≤ 10[^3^]$
* $Î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") ==
