Fişierul intrare/ieşire:cezar.in, cezar.outSursăOJI 2007, clasele 11-12
AutorRodica PinteaAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cezar

In Roma antica exista N asezari senatoriale distincte, cate una pentru fiecare dintre cei N senatori ai Republicii. Asezarile senatoriale sunt numerotate de la 1 la N, intre oricare doua asezari existand legaturi directe sau indirecte. O legatura este directa daca ea nu mai trece prin alte asezari senatoriale intermediare. Edilii au pavat unele dintre legaturile directe dintre doua asezari (numind o astfel de legatura pavata "strada"), astfel incat intre oricare doua asezari senatoriale sa existe o singura succesiune de strazi prin care se poate ajunge de la o asezare senatoriala la cealalta.
Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste 1 ban pentru ca a fost transportat cu lectica pe acea strada.
La alegerea sa ca prim consul, Cezar a promis ca va dota Roma cu o lectica gratuita care sa circule pe un numar de K strazi ale Romei astfel incat orice senator care va circula pe strazile respective, sa poata folosi lectica gratuita fara a plati. Strazile pe care se deplaseaza lectica gratuita trebuie sa fie legate intre ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).
In plus, Cezar a promis sa stabileasca sediul salii de sedinte a Senatului intr-una dintre asezarile senatoriale aflate pe traseul lecticii gratuite. Problema este de a alege cele K strazi si amplasarea sediului salii de sedinte a Senatului astfel incat, prin folosirea transportului gratuit, senatorii, in drumul lor spre sala de sedinte, sa faca economii cat mai insemnate. In calculul costului total de transport, pentru toti senatorii, Cezar a considerat ca fiecare senator va calatori exact o data de la asezarea sa pana la sala de sedinte a Senatului.

Cerinta

Scrieti un program care determina costul minim care se poate obtine prin alegerea adecvata a celor K strazi pe care va circula lectica gratuita si a locului de amplasare a salii de sedinta a Senatului.

Date de intrare

Fisierul cezar.in contine:

  • pe prima linie doua valori N K separate printr-un spatiu reprezentand numarul total de senatori si numarul de strazi pe care circula lectica gratuita
  • pe urmatorele N-1 linii se afla cate doua valori i j separate printr-un spatiu, reprezentand numerele de ordine a doua asezari senatoriale intre care exista strada.

Date de iesire

Pe prima linie a fisierului cezar.out se va scrie costul total minim al transportarii tuturor senatorilor pentru o alegere optima a celor K strazi pe care va circula lectica gratuita si a locului unde va fi amplasata sala de sedinte a Senatului.

Restrictii

  • 1 < N ≤ 10000
  • 0 < K < N
  • 1 ≤ i, j ≤ N, i ≠ j
  • Oricare doua perechi de valori de pe liniile 2, 3,..., N din fisierul de intrare reprezinta doua strazi distincte.
  • Perechile din fisierul de intrare sunt date astfel incat respecta conditiile din problema.
  • Pentru 25% din teste N ≤ 30, pentru 25% din teste 30 < N ≤ 1000, pentru 30% din teste 1000 < N ≤ 3000, pentru 10% din teste 3000 < N ≤ 5000, pentru 10% din teste 5000 < N ≤ 10000.

Exemplu

cezar.incezar.out
13 3
1 2
2 3
2 8
7 8
7 5
5 4
5 6
8 9
8 10
10 11
10 12
10 13
11

Explicatie

Costul minim se obtine, de exemplu, pentru alegerea celor 3 strazi intre asezarile 5-7, 7-8, 8-10 si a salii de sedinte a Senatului in asezarea 8 (dupa cum este evidentiat in desen).
Exista si alte alegeri pentru care se obtine solutia 11.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content