Hide

Problem H
Ekorren i trädet

En ekorre bor i ett träd med $N$ noder och $N-1$ kanter. Varje kant har längd 1 och kopplar ihop två noder. I några av noderna har ekorren gömt nötter, som han nu vill samla in. Om ekorren börjar vid nod 1 (roten av trädet), vad är kortaste avståndet han behöver gå för att hämta alla nötter och återvända till nod 1? Ekorren kan bära flera nötter samtidigt.

Det är garanterat att man kan ta sig mellan alla par av noder genom att gå via en sekvens av kanter.

Indata

Den första raden innehåller två heltal $N$ och $K$ ($1 \le K\le N \le 100\, 000$) – antal noder i trädet och antal noder med nötter på. Den andra raden innehåller $K$ unika heltal – noderna där ekorren har gömt nötter. Noderna är indexerade 1 till $N$. Därefter följer $N-1$ rader. Varje rad innehåller två heltal $1 \le a,b \le N$ som betyder att det går en kant mellan nod $a$ och nod $b$.

Utdata

Skriv ut ett heltal – det kortaste avståndet ekorren behöver gå för att hämta alla nötter.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$20$

Den $i$:te kanten går mellan nod $i$ och $i+1$ (för $1\le i \le N-1$)

$2$

$40$

$1 \le K \le N \le 1000$

$3$

$40$

Inga ytterligare begränsningar

Exempelfall

Sample Input 1 Sample Output 1
5 2
4 5
1 2
2 3
2 4
1 5
6
Sample Input 2 Sample Output 2
10 4
5 4 8 6
2 7
1 2
4 2
2 5
5 3
5 10
6 7
8 4
9 4
12

Please log in to submit a solution to this problem

Log in