Fişierul intrare/ieşire:aiacupalindroame.in, aiacupalindroame.outSursăGrigore Moisil 2017, 11-12
AutorVlad PotraAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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ă.

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ă:

  1. Drumul de la x la LCA (x, y) şi drumul de la y la LCA (x, y) au aceeasi lungime.
  2. Şirul de caractere corespunzător lanţului de la x la y, care trece prin LCA (x, y) să fie palindrom.

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 ≤ 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ţ.

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.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ Q ≤ 500.000
  • Pentru teste în valoare de 25 de puncte N ≤ 1.000 şi Q ≤ 5.000
  • Pentru teste în valoare de 60 de puncte N ≤ 20.000 şi Q ≤ 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

Exemplu

aiacupalindroame.inaiacupalindroame.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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?