Crisan Daniela Alexandra (URA) 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ța
Se dă un arbore cu N noduri înrădăcinat în 1 și un șir A de lungime M , cu 1≤A[i]≤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:
\[
\sum_{st = 1}^{M} \sum_{dr = st}^{M} \operatorname{lca}(A[st], A[st+1], \ldots, A[dr])
\]
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 ≤ N ≤ 2000001 ≤ M ≤ 400000- Pentru teste în valoare de
10de puncte, pentru oricarei>1,A[i]este strămoșul luiA[i-1] - Pentru alte teste în valoare de
20de puncte, arborele este un lanț - Pentru teste în valoare de
10de puncte,1 ≤ N, M ≤ 1000 - Pentru teste în valoare de
10de puncte,1000 ≤ N, M ≤ 3000 - Pentru teste în valoare de
25de puncte,3000 ≤ N, M ≤ 100000 - Pentru restul testelor se păstrează restricțiile inițiale din enunț
- În varianta publicată pe platforma PBInfo, față de cea utilizată în concurs, a fost adăugat
Testul 12, în valoare de1punct. Această modificare are scopul de a încuraja o abordare mai eficientă a problemei și nu a afectat evaluarea soluțiilor trimise în timpul concursului.
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