Fişierul intrare/ieşire:taxi2.in, taxi2.outSursăAlgoritmiada 2016 Runda 1 Seniori
AutorAdrian Budau, Mihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.8 secLimită de memorie54096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Taxi2

Ne aflăm în anul 2050, iar metroul din Drumul Taberei a fost inaugurat recent. Firmele de Taxi consideră că viaţa bucureştenilor a devenit acum prea bună, aşa că au hotărât să-i pedepsească mărind costurile unei călătorii cu taxi-ul. Mai exact, un client care face o comandă telefonică trebuie acum să plătească taxi-ul şi pentru distanţa pe care acesta o parcurge de la locaţia sa iniţială până la adresa clientului. Mai mult, dacă la un moment dat există M comenzi telefonice care trebuie satisfăcute şi M taximetrişti liberi, dispeceratul va cupla taximetriştii cu comenzile astfel încât distanţa totală parcursă de către cei M taximetrişti până la adresele corespunzătoare să fie maximă. Noi dorim să studiem costurile unui asemenea cuplaj, în funcţie de poziţiile iniţiale ale taximetriştilor şi ale clienţilor.

Bucureştiul a devenit între timp un arbore neorientat cu N noduri şi distanţe pozitive pe muchii (o transformare tragică, dar care nu a înrăutăţit neaparat traficul). Fiecare dintre cei M taximetrişti se poate afla în oricare din cele N noduri. Acelaşi lucru este valabil pentru fiecare dintre cei M clienţi. Un nod poate găzdui un număr nelimitat de taximetrişti şi/sau clienţi. Astfel, există în total N2M configuraţii diferite ale poziţiilor taxi/client. Dacă un taximetrist care se află în nodul X este cuplat cu o comandă din nodul Y, costul călătoriei sale va fi egal cu distanţa dintre nodurile X şi Y. Întrebarea noastră este următoarea: Dacă S ar fi suma cuplajelor de cost maxim pentru toate cele N2M configuraţii posibile, ce valoare ar avea S modulo 109 + 7?

Date de intrare

Fişierul de intrare taxi2.in va conţine pe prima sa linie numerele N şi M, semnificând numărul de noduri ale Bucureştiului, respectiv numărul de taxi-uri şi numărul de clienţi. Următoarele N - 1 linii vor conţine un triplet a b dist cu semnificaţia că există o muchie neorientată între nodurile a şi b de distanţă dist.

Date de ieşire

În fişierul de ieşire taxi2.out se va afla valoarea S modulo 109 + 7.

Restricţii

  • 1 ≤ N, M ≤ 1.000
  • Pentru 70% din punctaj, 1 ≤ N, M ≤ 100
  • Pentru fiecare muchie a arborelui, 1 ≤ dist ≤ 10.000

Exemplu

taxi2.intaxi2.out
2 1
1 2 5
10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

Explicaţie

Există 22 = 4 configuraţii. În 2 din ele taxi-ul şi clientul se află în acelaşi nod, deci costul e 0. În celelalte 2 se află în noduri diferite deci costul e 5.