Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-12-12 23:12:45.
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

Date de intrare

Fişierul de intrare drum7.in contine pe prima linie numarul n de noduri din arbore. Urmatoarele n-1 linii contin cate o pereche de numere, reprezentand muchiile arborelui.
Linia n+1 contine numarul k de noduri care trebuiesc vizitate.
Linia n+2 contine 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 afisa un singur numar, distanta minima care trebuie parcursa.

Restricţii

  • 1 ≤ n ≤ 100000
  • 1 ≤ k ≤ n
  • Pentru 30% din teste se garanteaza ca drumul optim este un lant.
  • Pentru alte 30% din teste se garanteaza 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 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?