== include(page="template/taskheader" task_id="aiacupalindroame") ==

== include(page="template/taskfooter" task_id="aiacupalindroame") ==
 

Se dă un arbore cu N noduri numerotate de la $1$ la $N$ cu rădăcina în nodul $1$. Muchiilor arborelui li se asociază caractere litere mici ale alfabetului englez $(a, b, …, z)$. Cel mai apropiat strămoş comun sau pe scurt LCA a două noduri $x$ şi $y$ este nodul $z$ care este strămoş al ambelor noduri $x$ şi $y$ şi are cea mai mare adâncime de la rădăcină.
 
h2. Cerinţă
 
Se dau $Q$ întrebări de forma $x y$  – unde $x$ şi $y$ sunt două noduri din arbore. Se cere să se răspundă pentru fiecare intrebare dacă $(x, y)$ este **LCA-palindrom** sau nu. Spunem că $(x, y)$ e **LCA-palindrom** dacă:
 
# Drumul de la $x$ la $LCA (x, y)$ şi drumul de la $y$ la $LCA (x, y)$ au aceeasi lungime.
# Şirul de caractere corespunzător lanţului de la $x$ la $y$, care trece prin $LCA (x, y)$ să fie palindrom.
 
h2. Date de intrare
 
Pe prima linie a fişierului $aiacupalindroame.in$ se găsesc două numere naturale $N$ si $Q$, separate cu spaţiu, cu semnificaţia din enunţ. Pe a doua linie din fişier se află $N-1$ numere, separate prin câte un spaţiu, cel de al $K$-lea număr $(1 &le; K < N)$ reprezentând tatăl nodului $K+1$. Pe a treia linie se află un şir de caractere cu exact $N-1$ caractere mici ale alfabetului englez, cel de al $K$-lea caracter reprezentând costul muchiei dintre nodurile $K+1$ şi tatăl său. Pe fiecare din următoarele $Q$ linii se află o pereche $x$ şi $y$, separate de un spaţiu, cu semnificaţia din enunţ.
 
h2. Date de ieşire
 
Fişierul de ieşire $aiacupalindroame.out$ va conţine $Q$ linii. Pe fiecare linie se va scrie $0$  dacă răspunsul la întrebare este fals, respectiv $1$ dacă răspunsul la întrebare este adevărat.
 
h2. Restricţii
 
* $1 &le; N &le; 100.000$
* $1 &le; Q &le; 500.000$
* Pentru teste în valoare de $25$ de puncte $N &le; 1.000$ şi $Q &le; 5.000$
* Pentru teste în valoare de $60$ de puncte $N &le; 20.000$ şi $Q &le; 100.000$
* Se garanteaza ca pentru fiecare query nodurile sunt distincte.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte
* Se vor acorda $10$ puncte din oficiu
 
h2. Exemplu
 
table(example). |_. aiacupalindroame.in |_. aiacupalindroame.out |
| 9 5
1 1 1 2 2 3 4 4
abaebaeb
2 7
2 4
1 9
5 8
5 9
| 0
1
0
1
0
|
 
h3. Explicaţie
 
Pentru întrebarea (2, 7), $LCA (2, 7)$ = 1, distanţa dintre nodul 1 şi nodul 2 este diferită faţă de cea dintre nodul 1 şi nodul 7, deci răspunsul este fals.
Pentru întrebarea (2, 4), LCA = 1, distanţa de la 1 la 2 este egală cu cea de la 1 la 4, iar concatenarea drumurilor este “aa”, care e palindrom, deci răspunsul este adevărat.
Pentru întrebarea (1, 9), LCA = 1, distanţele de la 1 la 1 şi de la 1 la 9 diferă, deci  răspunsul este fals.
Pentru (5, 8), LCA = 1, disţanele sunt egale, sirul este “eaae” deci, răspunsul e adevărat.
Pentru (5, 9), LCA = 1, sirul este “eaab”, care nu e palindrom, deci fals.
 
 
 
== include(page="template/taskfooter" task_id="aiacupalindroame") ==