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

• 1 ≤ N ≤ 100 000
• 1 ≤ c ≤ 1 000 000 000
• Pentru teste în valoare de 10 puncte C=1 si N ≤ 100
• Pentru alte teste în valoare de 45 puncte C=1 si N ≤ 50 000
• Pentru alte teste în valoare de 20 puncte C=1 si N ≤ 100 000
• Pentru alte teste în valoare de 12 puncte C=2 si N ≤ 50 000
• Pentru alte teste în valoare de 13 puncte C=2 si N ≤ 100 000

Exemplu

Cum se trimit solutii?