Fişierul intrare/ieşire:nespus.in, nespus.outSursăAlgoritmiada 2018 Runda Maraton
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nespus

Tanaka iar a dat de încurătură! Cum în scurt timp urmează festivalul Nespus, el trebuie să găsească cazare pentru cei K-1 (cu el K) prieteni ai săi în oraşul Julc. Oraşul Julc este dispus sub forma unui arbore cu N noduri (nodurile sunt intersecţii, iar muchiile străzi). Fiecare intersecţie este dotată cu un hotel, dar, din cauza aglomeraţiei festivalului, fiecare hotel are loc doar de un om. Pe fiecare stradă va cânta 24 din 24 câte o trupă; fiecare trupă este caracterizată de un indice de caterincă.
Grupul lui Tanaka va vizita doar subarborele minim ce conţine toate hotelurile lor (fiind foarte obosiţi de la dansat, nu au chef să se plimbe mult). Tanaka nu vrea ca prietenii săi să se certe din cauza diferenţelor de caterincă a diverselor trupe din zona vizitată, şi nu îi pasă foarte mult de caterinca trupelor în sine. Îl puteţi ajuta pe Tanaka să găsească care ar fi diferenţa minimă posibilă dintre indicele de caterincă maxim, respectiv minim, al tuturor trupelor din zona vizitată, pentru oricare mod de a alege K hoteluri ?

Date de intrare

Fişierul de intrare nespus.in va conţine, pe primul rând, pe N şi K.
Pe următoarele N-1 rânduri vor fi descrise străzile Julc-ului, câte una pe un rând. Fiecare stradă va fi reprezentată de un triplet x y z, care reprezintă că există o stradă între intersecţiile cu indicii x şi y, pe care cântă o trupă cu indicele de caterincă egal cu z.

Date de ieşire

Fişierul de ieşire nespus.out va conţine diferenţa cerută.

Precizări şi restricţii

  • 2 ≤ K ≤ N (Tanaka nu vrea să meargă singur la festival ☺).
  • 1 ≤ indicele de caterincă a oricărei trupe ≤ 1.000.000.000
  • Subtask 1 (feedback testul 1) - 10 puncte: 2 ≤ N ≤ 100
  • Subtask 2 (feedback testul 3) - 20 puncte: 2 ≤ N ≤ 1.000
  • Subtask 3 (feedback testele 7, 8 si 12) - 30 puncte: 2 ≤ N ≤ 50.000
  • Subtask 4 (feedback testele 13, 14 si 20) - 40 puncte: 2 ≤ N ≤ 100.000
  • Pentru a usura implementarea, străzile sunt date în ordinea crescătoare a indicelui de caterincă a trupei de pe ele

Exemplu

nespus.innespus.outExplicaţie
4 3
2 3 1
3 4 2
1 2 100
1Se aleg hotelurile din intersecţiile 2, 3, 4
6 3
2 1 3
5 3 4
6 1 6
3 2 9
4 2 12
3Se aleg hotelurile din intersecţiile 1, 2, 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?