Busca Periódica

Foi feita uma análise da evolução dos estados quânticos possíveis de um sistema de partículas, resultando numa árvore enraizada de N estados. Cada estado, com exceção do estado raiz, é conectado a seu estado pai por uma aresta que possui um rótulo de uma letra latina minúscula de a a z. Esse rótulo descreve o tipo de interferência que levou o sistema a ter um colapso para outro estado. A sequência de interferências de um estado é denida como a concatenação dos rótulos das arestas no caminho da raiz até esse estado.

Para cada estado, definímos a periodicidade mínima de sua sequência como o menor inteiro $P ≥ 1$ tal que a sequência pode ser obtida repetindo uma sequência menor de tamanho P múltiplas vezes (no mínimo duas vezes). Caso não exista nenhum inteiro $P ≥ 1$ válido, a sequência é considerada de periodicidade $0$. A sequência vazia da raiz é considerada de periodicidade $0$.

Estamos interessados em estudar interferências periódicas dentro do sistema de partículas, então sua tarefa é determinar, dentre todos os estados a partir da raiz, o maior valor de periodicidade mínima das suas respectivas sequências de interferências.

A primeira linha contém um inteiro $N$ $(2 ≤ N ≤ 10^5 )$, o número de estados. A segunda linha contém $N − 1$ inteiros $P_1 , P_2 , ..., P_N −1$ $(1 ≤ Pi ≤ i)$, onde o estado $i + 1$ está conectado ao estado $P_i$ . A terceira linha contém uma sequência de $N − 1$ letras latinas minúsculas, onde o caractere $i$ representa o rótulo na aresta entre os estados $P_i$ e $i + 1$.

Imprima um único inteiro representando o maior período mínimo entre todas as sequências formadas pelos caminhos da raiz até cada estado.