| Fişierul intrare/ieşire: | drum7.in, drum7.out | Sursă | FMI No Stress 10 |
| Autor | Seritan Luca | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Drum7
După ce a călătorit peste şapte mări si şapte ţări, Făt-Frumos a ajuns pe tărâmul unde Cosânzeana a fost răpită de zmeu şi închisă într-un turn.
Se ştie că acest tărâm are forma unui arbore cu n noduri, printre care există k noduri unde este situat câte un turn.
Făt-Frumos nu ştie în care turn se află prinţesa, aşa că vrea să pună la cale un plan prin care să treacă pe la fiecare dintre acestea, astfel încât sa parcurgă o distanţă cât mai mică.
Ştiind că Făt-Frumos îşi poate începe căutarea din orice nod si fiecare muchie are lungimea 1, care este lungimea minimă a unui drum care trece prin fiecare dintre cele k noduri măcar o data?
Date de intrare
Fişierul de intrare drum7.in conţine pe prima linie numărul n de noduri din arbore. Următoarele n-1 linii conţin câte o pereche de numere, reprezentând muchiile arborelui.
Linia n+1 conţine numărul k de noduri care trebuie vizitate.
Linia n+2 conţine un sir de k numere distincte, indicii nodurilor ce trebuie vizitate.
Date de ieşire
În fişierul de ieşire drum7.out se va afişa un singur număr, distanta minima care trebuie parcursa.
Restricţii
- 1 ≤ n ≤ 100000
- 1 ≤ k ≤ n
- Pentru 30% din teste se garantează ca drumul optim este un lanţ.
- Pentru alte 30% din teste se garantează ca n ≤ 10000 si k ≤ 100
Exemplu
| drum7.in | drum7.out |
|---|---|
| 15 1 7 2 7 3 6 4 12 5 9 6 14 7 9 8 12 10 9 11 12 12 9 13 7 14 4 15 14 4 7 14 2 3 | 7 |
| 15 1 10 2 1 3 15 4 11 5 7 6 5 7 3 8 4 9 1 11 10 12 15 13 10 14 7 15 10 5 12 8 5 9 14 | 15 |
