URI Online Judge | 2883

Hipótese Policial

Por Maratona de Programação SBC 2018 BR Brazil

Timelimit: 8

O sistema de transporte público da Nlogônia conta com uma rede expressa conectando os principais pontos turísticos do país. São usados N −1 trens-bala para conectar N atrações de modo que a partir de um dos pontos turísticos é possível alcançar qualquer outro ponto usando apenas essa rede expressa. Como em qualquer lugar do mundo, é comum que haja pichações nas estações de trem. O que chamou a atenção da polícia do país é o fato de que em cada uma das estações é possível encontrar exatamente uma letra pichada com um estilo específico. A hipótese é de que criminosos podem estar alterando as pichações como meio de comunicação e portanto decidiu-se criar um sistema capaz de monitorar as pichações e suas alterações. Dado um padrão P, a descrição das conexões entre as estações e as letras suspeitas em cada uma das estações, sua tarefa é escrever um programa capaz de lidar com as seguintes operações:

Entrada

A primeira linha contém dois inteiros N e Q (1 ≤ N, Q ≤ 105 ), representando o número de estações e a quantidade de operações que devem ser processadas. A segunda linha contém o padrão P monitorado (1 ≤ |P| ≤ 100). A terceira linha contém uma string S com N caracteres representando as letras inicialmente associadas a cada uma das estações. Cada uma das N − 1 linhas seguintes contém dois inteiros u e v indicando que existe um trem-bala entre as estações u e v. As Q linhas seguintes descrevem as operações que devem ser processadas conforme descrito acima.

Saída

Seu programa deve imprimir uma linha para cada operação do tipo 1 contendo um inteiro que representa o número de ocorrências do padrão P no caminho analisado.

Exemplos de Entrada Exemplos de Saída

6 7

lol

dlorlx

1 2

1 3

3 4

3 5

5 6

1 2 6

2 3 l

2 6 l

2 5 o

1 2 6

2 1 o

1 6 2

0

1

2

5 2

aba

ababa

1 2

2 3

3 4

4 5

1 1 5

1 5 1

2

2

4 4

xtc

xtzy

1 2

2 3

3 4

1 1 3

2 3 c

1 1 3

1 3 1

0

1

0