drum7

Drum7

== include(page="template/taskheader" task_id="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?

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

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.

h2. Date de ieşire

În fişierul de ieşire $drum7.out$ se va afisa un singur numar, distanta minima care trebuie parcursa.

În fişierul de ieşire $drum7.out$ se va afişa un singur număr, distanta minima care trebuie parcursa.

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

* 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

h2. Exemplu

| 15
|

h3. Explicaţie
In primul exemplu, un drum optim este $7-9-12-4-14-6-3$ si are lungime 7.

h4. 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
== include(page="template/taskfooter" task_id="drum7") ==