| Fişierul intrare/ieşire: | aiacupalindroame.in, aiacupalindroame.out | Sursă | Grigore Moisil 2017, 11-12 |
| Autor | Vlad Potra | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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ă:
- 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.
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.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 |
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.
