405338: GYM101908 H Police Hypothesis

The public transport system of Nlogônia has an express network connecting the main points of interest of the country. There are $$$N−1$$$ bullet trains connecting $$$N$$$ attractions such that from one of the points of interest you can reach any other using only this network.

As anywhere in the world, it is common that there is graffiti on the train stations. What caught the attention of the police of the country is the fact that in each one of the stations it is possible to find exactly one letter pinned with a specific style. The hypothesis is that criminals may be changing the graffiti as a means of communication and, therefore, it was decided to create a system capable of monitoring the graffiti and its amendments.

Given a pattern $$$P$$$, the description of the connections between stations and the suspicious letters in each of them, your task is to write a program able to deal with the following operations:

• 1 $$$u$$$ $$$v$$$: print how many times the pattern $$$P$$$ occurs in the path from $$$u$$$ to $$$v$$$ if we look at the string of characters associated with the consecutive vertices of the path;
• 2 $$$u$$$ $$$x$$$: change the suspicious letter at the station $$$u$$$ to $$$x$$$.

The first input line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), representing the number of stations and the number of transactions that must be processed. The second line contains the pattern $$$P$$$ monitored ($$$1 \leq |P| \leq 100$$$). The third line contains a string with $$$N$$$ characters representing the letters initially associated with each of the stations. Each of the following $$$N−1$$$ lines contains two integers $$$u$$$ and $$$v$$$ indicating that there is a bullet train between $$$u$$$ and $$$v$$$. The following $$$Q$$$ lines describe the operations that must be processed as described above.

Your program should print a line for each operation of type 1 containing an integer that represents the number of occurrences of the pattern $$$P$$$ on the way.

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

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