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