408520: GYM103181 A Crop Circles

Your favourite local farmer firmly believes that aliens do, in fact, exist. Even more so, he is sure that they are trying to communicate with him - through crop circles, no less.

These circles are quite peculiar - they are shaped in the form of a tree, and it seems like each circle contains one letter. The farmer is absolutely convinced that the letters represent, in fact, a codified message - simply because he has dreamed of a string which might be found (or not) as a chain in the tree of crop circles.

Since it is hard to believe, you must verify this. Given this tree with N nodes, each of them containing a lowercase letter of the Latin alphabet, how often does the string that the farmer has dreamed of occur as a simple path?

The first line of input will contain an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of nodes, and a string $$$s$$$ of at least $$$1$$$ and at most $$$10^{5}$$$ characters, representing the string that the farmer has dreamed of. Note that the string only consists of lowercase Latin alphabet letters: namely, for any element of the string, $$$s_i$$$, it holds that ($$$'a'$$$ $$$\leq s_i \leq$$$ $$$'z'$$$).

The next line will contain another string $$$x$$$ of $$$N$$$ characters. Character $$$x_i$$$ represents the letter which is found at node $$$i$$$.

Next will follow $$$N-1$$$ other lines, each of them with two integers $$$a$$$, $$$b$$$ ($$$1 \leq a,b \leq N$$$). These lines represent that an edge is drawn from node $$$a$$$ to node $$$b$$$.

The output should only have one integer - the number of times the farmer's string has been found as a simple path in the given tree.

Two simple paths of the same length $$$k$$$: $$$x_1, x_2, ..., x_k$$$ and $$$y_1, y_2, ..., y_k$$$ are considered different if there is at least one $$$i$$$ such that $$$x_i$$$, $$$y_i$$$ are different.

13
aba
babaabaaabbaa
1 2
1 7
1 9
2 3
3 4
3 5
6 7
7 8
9 10
10 11
11 12
11 13

14