Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | trenbus.in, trenbus.out | Sursă | Lot Seniori Campulung 2018, baraj 3 |
| Autor | Andrei Popa, Tamio-Vesa Nakajima | Adăugată de |  Andrei Boaca •hhhhhhh |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Trenbus
Se dau doi arbori neorientaţi cu N noduri etichetate de la 1 la N şi costuri pe muchii. Primul arbore se numeşte TREN, iar al doilea se numeşte BUS. Pentru două noduri A şi B şi un arbore T definim d(A,B,T) = valoarea maximă a unei muchii de pe drumul elementar dintre nodurile A şi B în arborele T.
Suntem interesaţi de perechile de valori X şi Y cu proprietatea că d(X,Y,TREN)+d(X,Y,BUS) este minim posibil.
În funcţie de valoarea unui parametru C din datele de intrare, trebuie să afişaţi suma minimă cerută, respectiv numărul de perechi de valori (X,Y) care se realizează această valoare minimă.
Date de intrare
Pe primul rând al fişierului de intrare trenbus.in se găsesc numerele naturale C şi N.
Pe următoarele N-1 rânduri se găsesc muchiile neorientate care descriu arborele TREN, iar pe următoarele N-1 rânduri se găsesc muchiile neorientate care descriu arborele BUS. Fiecare muchie este descrisă de 3 numere naturale a b c, reprezentând capetele muchiei respectiv costul.
Date de ieşire
Pe singurul rând al fişierului de ieşire trenbus.out se vor tipări:
- dacă C=1, doar suma cerută,
- dacă C=2, suma cerută şi numărul de perechi separate printr-un spaţiu.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| trenbus.in | trenbus.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
