== 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?
Poveste şi cerinţă...
h2. 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.
Fişierul de intrare $drum7.in$ ...
h2. 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.
În fişierul de ieşire $drum7.out$ ...
h2. 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
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. 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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 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
|
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
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="drum7") ==
