Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-12-16 11:15:19.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:drum7.in, drum7.outSursăFMI No Stress 10
AutorSeritan LucaAdăugată defminostress9FMI No Stress 9 •fminostress9
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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

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.indrum7.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

Explicaţie
In primul exemplu, un drum optim este 2-7-9-12-4-14-6-3 si are lungime 7.
In cel de-al doilea exemplu, un drum optim este 8-4-11-10-1-9-1-10-15-12-15-3-7-14-7-5 si are lungime 15

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?