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 |