Allca

RAU-Gigel și Praștie împodobeau bradul de Crăciun și s-au gândit că ar merge niște colinde. Căutând, au dat de cuvântul “carol”, care evident le-a amintit de orele de informatică. Cu asta și copacul din fața lor în minte, s-au gândit la următoarea problemă, pe care vă roagă să o rezolvați.

Cerință

Se dă un arbore cu $N$ noduri înrădăcinat în $1$ și un șir $A$ de lungime $M$, cu $1 \leq A[i] \leq N$. Definim nivelul unui nod ca fiind distanța față de rădăcină și strămoșul unui nod $x$ ca fiind oricare nod $y$ de pe drumul de la $x$ la rădăcină. De asemenea, $lca(V)$, unde $V$ este un șir, reprezintă nodul de nivel maxim care este strămoș pentru toate nodurile din șirul $V$. Să se calculeze sumă după $lca(V)$, unde $V$ este fiecare subsecvență a șirului $A$. Mai formal, să se afle:

Date de intrare

Fișierul de intrare allca.in conține pe prima linie numărul $N$ de noduri din arbore. Pe următoarele $N - 1$ linii avem descrierea arborelui, câte o muchie pe fiecare linie. Pe linia $N + 1$ se află $M$, iar pe linia $N + 2$ șirul $A$.

Date de ieșire

Fișierul allca.out va conține, pe prima linie, un singur număr întreg, suma căutată.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq M \leq 400 \ 000$
• Pentru teste în valoare de $10$ de puncte, pentru oricare $i>1, A[i]$ este strămoșul lui $A[i-1]$
• Pentru alte teste în valoare de $20$ de puncte, arborele este un lanț
• Pentru teste în valoare de $10$ de puncte, $1 \leq N, M \leq 1 \ 000$
• Pentru teste în valoare de $10$ de puncte, $1 \ 000 \leq N, M \leq 3 \ 000$
• Pentru teste în valoare de $25$ de puncte, $3 \ 000 \leq N, M \leq 100 \ 000$
• Pentru restul testelor se păstrează restricțiile inițiale din enunț

Exemplul 1

allca.in

2
1 2
2
2 1

allca.out

4

Explicație

$lca(2)+lca(1)+lca(2,1)=2+1+1=4.$

Exemplul 2

allca.in

5
1 2
2 3
3 4
4 5
8
4 1 2 4 2 4 2 2

allca.out

64

Exemplul 3

allca.in

3	
1 2
1 3
5
1 3 2 2 1

allca.out

20