| Fişierul intrare/ieşire: | nespus.in, nespus.out | Sursă | Algoritmiada 2018 Runda Maraton |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | nespus.out | Explicaţie |
|---|---|---|
| 4 3 2 3 1 3 4 2 1 2 100 | 1 | Se 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 | 3 | Se aleg hotelurile din intersecţiile 1, 2, 6 |
