Fişierul intrare/ieşire:trenbus.in, trenbus.outSursăLot Seniori Campulung 2018, baraj 3
AutorAndrei Popa, Tamio-Vesa NakajimaAdăugată deandreicoman299Coman Andrei andreicoman299
Timp execuţie pe test5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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

trenbus.intrenbus.outExplicaţie
1 3
1 2 5
2 3 6
1 3 1
2 3 2
7
C=1
Se afişează doar suma minimă.
Generată de x = 1, y = 2 sau respectiv x = 1, y = 3.
2 5
1 2 2
2 5 3
2 4 7
2 3 2
1 2 4
2 3 4
3 4 3
4 5 2
6 4
C=2
Suma minimă este 6, iar numărul perechilor de noduri ce generează această sumă minimă este 4.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?