Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | paths.in, paths.out | Sursă | RMI 2021 |
| Autor | Alexandra Udristoiu | Adăugată de |  Udristoiu Alexandra Maria •alexandra_udristoiu |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Paths
Portocal, pisica cea portocalie, a găsit un arbore (graf neorientat conex aciclic) cu N noduri numerotate de la 1 la N. Pe fiecare muchie i ($1 &le i < N$) care conectează nodurile xi şi yi se află ci gustări pentru pisici.
Portocal poate alege exact K nodurii; pentru fiecare dintre nodurile alese, el va merge pe drumul de la rădăcina arborelui la nodul ales şi va mânca gustările de pe muchiile pe care trece. Evident, el poate mânca gustările de pe o muchie o singură dată. Deoarece Portocal este o pisică foarte curioasă din fire, el ar vrea să afle care este numărul maxim
de gustări pe care le poate mânca, alegând optim cele K noduri, dacă rădăcina arborelui era nodul i, pentru fiecare i de la 1 la N.
Date de intrare
Fişierul de intrare paths.in ...
Date de ieşire
În fişierul de ieşire paths.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| paths.in | paths.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
